# 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

### 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.

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 2  ## Sorted Squared Array

in  