Here’s the problem statement:
Given 2 arrays of integers, tell if the second array is a valid subsequence of the first i.e. if the second array has some/all adjacent/nonadjacent elements of the first array in the same order.
For example:
Array 1: [1, 12, 45, 79, 0, 5, 6, 32]
Array 2: [12, 45, 79, 5, 32]
Output: true
Let’s dive into the solution:
Loop through the 2 arrays using two pointers i, j (both set to 0 initially of course) for the first and the second arrays respectively to check for the matching values in the 2 arrays in the following manner:
if the two values in the 2 arrays are same then increment i and j to look for the next matching value.
if the two values in the 2 arrays are not the same then increment only i on array1 to look for the element array2[j] in the first array.
When j reaches the end of array2 then we’ve found all elements of the second array in the first one and we can simply return true. If instead i reaches the end of array1 before j reaches the end of array2 then we’ve exhausted array1 and have not found all elements of array2 in it and so we must return false. Simplifying these 2 statements: when i and/or j reach the end of their arrays, then if j==array2.length then we must return true, else we must return false.
Time complexity: Since all elements in the 2 arrays will be visited once therefore the overall time complexity is O(M+N) where M, N are the lengths of array1 and array2 respectively.
Space complexity: O(1)
Here’s the code for this solution in Java:
public boolean isSubsequence(int[] array1, int[] array2) {
int i, j;
i = j = 0;
while(i<array1.length && j<array2.length) {
if(array2[j] == array1[i]) {
i++;j++;
}
else {
i++;
}
}
return j==array2.length;
}
Please do let me know if you find this article useful. Also, it’ll be great if you’d provide some feedback. To reach out, please leave a comment in the Contact section. Thanks! Happy Coding! 🙂
The Code Scribbbler 