Validate Subsequence with Time and Space complexity — Competitive Programming

Question — 2 (Level — Easy)

Code Wrestling | Competitive Programming

Welcome to the competitive series of Code Wrestling. Today, we are gonna solve another easy coding problem, Validate Subsequence.

We will find the Time and Space complexity of our solution and will also guide you to the process of finding an optimized solution.

Visit our YouTube channel for more interesting stuff Code Wrestling.

Github Repository Link: Github/ValidateSubsequence

Go to the previous question → Question — 1 (Two Number Sum)

Go to the next question → Question — 3 (Sorted Squared Array)

Code Wrestling

Question

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.

Sample Input:

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

Sample Output:

true

STOP HERE. And read the question again. Try to solve the question on your own and then proceed further to see our solution.

Solution

The objective here is to find whether the given sequence is a subsequence of an array or not.

For a sequence to be a valid subsequence, the order of the elements must be the same as of the given array, and all the elements must be present in the array.

Also, we need to take care of edge conditions like, a single element is also the subsequence of an array, and the whole array is a subsequence of itself.

Solution 1 with time complexity O(n²) and space complexity O(1).

Approach:

A simple solution will be to loop over both the sequence and the array. And have two flags, one is for maintaining the last element index found, and another one is to check whether that particular element is present from the sequence is present in the array or not.

1. Create two flags one as lastIndexFound = -1, and another as elementFound = false;
2. Loop over sequence and get the element, let’s name it as currentElement.
3. Now loop over all the elements in the given array, and check whether the currentElement is present or not.
4. If the currentElement is not present, that means the sequence is invalid (return false). But if the currentElement is present, then assign lastIndexFound as the index of element found in the array.
5. Now get the secondElement from the sequence, and this time again loop over the array, but start with the lastIndexFound + 1.
6. Repeat step 4 and 5.

Below is the code snippet: (C#)

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

private bool IsValidSubsequence(List<int> array, List<int> sequence)
{
     // Time Complexity - O(n^2)
     // Space Complexity - O(1)

     int lastIndexFound = -1;
     bool elementFound = false;
     // Loop over seq
     foreach (int currentElement in sequence)
     {
         elementFound = false;
         // For matching sequence look forward
         for (int j = lastIndexFound + 1; j < array.Count; j++)
         {
              if (array[j] == currentElement)
              {
                  elementFound = true;
                  lastIndexFound = j;
                  break;
              }
         }
         if (!elementFound)
         {
              return false;
         }
      }
      if (elementFound)
      {
         return true;
      } 
      // if none of element found
      return false;
}

Here the time complexity is O(n²) because of two for loops thus O(n * n) and thus O(n²) and space complexity is O(1).

This solution is simple but it has two for loops and thus is not a good one. Let’s see how we can optimize it. Can we remove one for loop?

Solution 2 with Time Complexity O(n) and Space Complexity O(1).

Let’s think of a way such that we can remove one for loop out of the two for loops.

Approach:

Let’s maintain two index, one is sequenceIndex and another one is arrayIndex. Now we will loop over ( a single while loop) till arrayIndex < array length and till sequenceIndex < sequence length.

Now if array element at arrayIndex (array[arrayIndex]) is equal to sequence element at sequenceIndex (sequence[sequenceIndex]) then we will increase both arrayIndex++ and sequenceIndex++, otherwise we will increase only arrayIndex++.

Now at the end if sequenceIndex == sequenceLength, then it’s a valid subsequence otherwise not.

1. Create two index arrayIndex = 0 and sequenceIndex = 0.
2. Loop untill arrayIndex < arrayLength and sequenceIndex < sequenceLength.
3. If array[arrayIndex] == sequence[sequenceIndex] then increase sequenceIndex and arrayIndex, otherwise just increase arrayIndex.
4. At the end, out of loop, check if sequenceIndex == sequenceLength, if all the element of sequence exists in array in same order then it will be true, otherwise false.

Look at the below code snippet, and try to understand the algorithm.

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

private bool IsValidSubsequence(List<int> array, List<int> sequence)
{
    // Time complexity - O(n)
    // Space complexity - O(1)
   
    int arrayIndex = 0;
    int sequenceIndex = 0;
   
    while (arrayIndex < array.Count
                                 && sequenceIndex < sequence.Count)
    {
        if (array[arrayIndex] == sequence[sequenceIndex])
        {
           sequenceIndex++;
        }
        arrayIndex++;
    }
   
    // if all elements of sequence is found in array
    // then sequenceIndex will be same as sequenceLength
    return sequenceIndex == sequence.Count;
}

Here the time complexity is O(n) because only one for loop and space complexity is O(1).

The solution is really good, but let’s see another solution that has the same time and space complexity.

An alternate way of writing the above code.

// array = [ 5, 1, 22, 25, 6, -1, 8, 10]
// sequence = [1, 6, -1, 10]
private bool IsValidSubsequence(List<int> array, List<int> sequence)
{
            int seqId = 0;
            foreach (int currentElement in array)
            {
                if (seqId == sequence.Count)
                    break;
                if (currentElement == sequence[seqId])
                {
                    seqId++;
                }
            }
            return seqId == sequence.Count;
}

Here also the time complexity is O(n) because only one for loop and space complexity is O(1).

Github Repository Link: Github/ValidateSubsequence

Go to the previous question → Question — 1 (Two Number Sum)

Go to the next question → Question — 3 (Sorted Squared Array)

Thank you so much for reading till the end. See you in the next article. Till then… HAPPY LEARNING!!

Do visit our YouTube channel Code Wrestling for more interesting stuff.

Code Wrestling