Validate subsequence
The Problem
Given two non-empty arrays of integers, write a function that determines whether the second array is a subsequence of the first one.
A subsequence of an array is a set of numbers that aren’t necessarily adjacent in the array but that are in the same order as they appear in the array.
For instance, the numbers
[1,3,4]
form a subsequence of the array[1,2,3,4]
, and so do the numbers[2,4]
.Note that a single number in an array and the array itself are both valid subsequences of the array.(
[1]
,[2]
,[3]
,[4]
and[1,2,3,4]
are all valid subsequences of[1,2,3,4]
)
Solution:
package main
func IsValidSubsequence(array []int, sequence []int) bool {
seqIdx := 0
arrIdx := 0
for seqIdx < len(sequence) && arrIdx < len(array) {
if sequence[seqIdx] == array[arrIdx] {
seqIdx++
}
arrIdx++
}
return seqIdx == len(sequence)
}
Complexity: O(n) time, O(1) space
Simplification
- For a
sequence []int
what does represent thelen(sequence)
?
The number of elements of that slice.
Example of []int{7, 8, 9, 11, 21,, -1, 3, 4}
:

- Is
sequence[len(sequence)]
part ofsequence
?
No. len(sequence)
is the first integer bigger than the last index of sequence
. Trying to access
sequence[len(sequence)]
would trigger an index out of range
error.
- Given a
[]int{}
, print all elements on a new line using a for-range loop.
package main
import "fmt"
func main() {
s := []int{1, 5, 7, 8, 5, 1, 4, 9}
for _, v := range s {
fmt.Println(v)
}
}
- Given a
[]int{}
, print all elements on a new line using a for loop.
package main
import "fmt"
func main() {
s := []int{1, 5, 7, 8, 5, 1, 4, 9}
for i := 0; i < len(s); i++ {
fmt.Println(s[i])
}
}
- Given a
[]int{}
, print all elements on a new line using a while loop.
package main
import "fmt"
func main() {
s := []int{1, 5, 7, 8, 5, 1, 4, 9}
i := 0
for i < len(s) {
fmt.Println(s[i])
i++
}
}