Close

How to check if sequence is a sub sequence of another

Given two arrays of numbers, how to check if the first sequence is a sub sequence of second sequence.

For example [3, 7, 11] is a sub-sequence of [9, 3, 1, 7, 5, 11]
where as [4, 8, 9] is not a sub-sequence of [6, 4, 9, 2, 8]

The algorithm here is simple. 

  • Let us assume two indices i, j point to the beginning of sub-sequence and sequence respectively.
  • Do the following until we reach the end of any sequence.
  • If both the elements are same, increment both indices.
  • Otherwise increment j only.

At the end of this iteration, if we have seen all the elements of sub-sequence in the given sequence, we are done! otherwise we have not found!

Here is the code in C++ which implements the above approach. This runs in O(n) time and O(1) space. For Python code click here. For Java code click here.

import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner reader = new Scanner(System.in);
int t = reader.nextInt();
while( t-- > 0 )
{
int n = reader.nextInt();
int i;
int [] seq = new int[n];
for( i = 0; i < n; i++ )
seq[i] = reader.nextInt();
int m = reader.nextInt();
int [] subSeq = new int[m];
for( i = 0; i < m; i++ )
subSeq[i] = reader.nextInt();
if( isSubSequence(subSeq,seq) )
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
public static boolean isSubSequence(int []subSeq, int []seq)
{
int i,j;
for( i = 0, j = 0; i < subSeq.length && j < seq.length; )
{
if (subSeq[i] == seq[j])
i++;
j++;
}
return i == subSeq.length? true:false;
}
}

Leave a Reply

Your email address will not be published. Required fields are marked *