Skip to main content

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

  1. For a sequence []int what does represent the len(sequence) ?

The number of elements of that slice.

Example of []int{7, 8, 9, 11, 21,, -1, 3, 4}:

  1. Is sequence[len(sequence)] part of sequence?

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.

  1. 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)
}
}
  1. 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])
}
}
  1. 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++
}
}