Coding Problem: Validate Subsequence

In this blog post, we will write a program to check if a sequence is valid subsequnce of input array.

Problem Statement:

Given two non-empty arrays of integers, write a method 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.

Sample Input:

array = [5, 1, 22, 25, 6, -1, 8, 10]
sequence = [1, 6, -1, 10]

Sample Output:

true

Solution:

Before going to the solution, let's understand about subsequnce. In mathematics, a subsequnce is a sequnce that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence (A, B, D) is a subsequnce of (A, B, C, D, E, F) obtained after removal of elements, C, E and F. The relation of one sequence being the subsequence of another is a preorder.

We have our main input array of integers, it is a sequence of integers. And if you were to remove some of the integers from this sequence, for example if you were to remove the integer 22 or maybe if you were to remove none of the integers, maybe you didn't remove 22, the remaining elements would be a subsequence of the orignal sequence.

Another way to think about subsequences when we're dealing with arrays is in order for an array to be a valid subsequence of another array, all of the integers in the potential subsequence have to not only appear in the original array but they also have to appear in the same order. They don't necessarily have to be adjacent. The sequence [1, 6, -1, 10] are not adjacent in our input given.

Solving the problem:

The first thing we need to realize is that we're gonna have to traverse both arrays that are given. We're gonna have to traverse the potential subsequence because that's the thing we're looking for. So how do we traverse them?

Because the order of the elements in a subsequence and in the original sequence matters, that means that at the very beginning, when we're just starting to look for our potential subsequence, we're really looking for the first element in the potential subsequence. So iterate through the main array, and look for the first integer in the potential subsequence. If you find that integer, keep on iterating through the main array, but now look for the second integer in the potential subsequence. Continue this process until you either find every integer in the potential subsequence or you reach the end of the main array. To do this, you'll have to declare a variable holding your position in the potential subsequence. At first, this position will be 0^th index in the sequence; as you find the sequence's integers in the main array, you'll increment the position variable until you reach the end of the sequence.

Time Complexity: O(n)

Space Complexity: O(1)

import java.util.List;

public class ValidateSubsequence {

    /**
     * Method to check if a sequence is a valid subsequence of main array.
     * @param array non-empty array of integers
     * @param sequence potential subsequence
     * @return boolean value it is valid subsequence or not
     */
    public static boolean isValidSubsequence(List<Integer> array, List<Integer> sequence) {
        int seqIdx = 0;
        for (Integer num : array) {
            if (seqIdx == sequence.size()) {
                break;
            }
            if (sequence.get(seqIdx).equals(num)) {
                seqIdx++;
            }
        }
        return seqIdx == sequence.size();
    }
}