Validate Subsequence with Time and Space complexity — Competitive Programming

Code Wrestling | Competitive Programming

Question

Sample Input:

Sample Output:

Solution

The objective here is to find whether the given sequence is a subsequence of an 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.
// 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;
}
  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.
// 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;
}
// 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;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store