# 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;}`

--

--