Validate Subsequence

Problem

We are given two arrays of integers nums and sequenceNums, and they are non-empty.

Check whether all the numbers in the sequenceNums appear in the nums and they appear in the same order. We call sequenceNums is a valid subsequence of nums. 

Concept:

A subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. (https://en.wikipedia.org/wiki/Subsequence)

Example:

Given sequence: [5, 1, 13, 15, 6, -2, 7, 10]

If we remove any of element from given sequence above without changing the order of remaining element, we get a subsequence.

Let’s say we remove 1, -2, 10 from the given sequence above, then [5, 13, 15, 6, 7] is a subsequence.

Example 1:

Input: nums = [5, 1, 13, 15, 6, -2, 7, 10], sequenceNums = [5, 13, 15, 6, 7]

Output: True

Explanation: [5, 13, 15, 6, 7] appear in [5, 1, 13, 15, 6, -2, 7, 10] and elements are appear in the order

Example 2:

Input: nums = [3,2,4], target = [3,10]

Output: false

Solution

The idea is to traverse through the array nums with two pointers. One pointer point to array nums, P1. Another pointer is pointed to sequenceNums, P2.

P1 and P2 start with 0 because array index start with 0

When we traverse through the array nums, we look if we can find the element the 1st element that P2 point to from sequenceNums.

From example above:

When P1 = 0, it points to 5 of array nums, and when P2 = 0, it points to 5 of array sequenceNums

• we found that the element from sequenceNumber exist in nums ( 5 = 5 ), so we

• • increase P2 from 0 to 1. In other word, we point P2 to the next element which is 13
  • increase P1 from 0 to 1. In other word, we point P1 to the next element which is 1

Why we move P1 to 1 and not back to 5? That’s because order matters (valid subsequence). Any future element from subsequenceNums need to be after 5.

When P1 = 1, it points to 1 of array nums, and when P2 = 1, it points to 13 of array sequenceNums

• we have 1 != 13, so we increase P1 from 1 to 2. In other word, we point P1 to the next element which is 13

We do this operation until the end of array nums.

At the end we know that if P2 == length of sequenceNums then there is a valid subsequence exist in nums

Complexity Analysis:

• Time Complexity: O(N), where N is the length of the array nums.

• Space Complexity: O(1), we don’t use any extra data structure. we just need integer variable for P1 and P2

Kotlin

Implementation 1

Implementation 2