Validate Subsequence

Code

Python

• Solution 1
• Solution 2

def isValidSubsequence(array, sequence):

arrIdx = 0

seqIdx = 0

while arrIdx < len(array) and seqIdx < len(sequence):

if array[arrIdx] == sequence[seqIdx]:

seqIdx += 1

arrIdx += 1

return seqIdx == len(sequence)

JavaScript

• Solution 1
• Solution 2

function isValidSubsequence(array, sequence) {

let arrIdx = 0;

let seqIdx = 0;

while (arrIdx < array.length && seqIdx < sequence.length) {

if (array[arrIdx] === sequence[seqIdx]) seqIdx++;

arrIdx++;

}

return seqIdx === sequence.length;

}

​

exports.isValidSubsequence = isValidSubsequence;

TypeScript

• Solution 1
• Solution 2

export function isValidSubsequence(array: number[], sequence: number[]) {

let arrIdx = 0;

let seqIdx = 0;

while (arrIdx < array.length && seqIdx < sequence.length) {

if (array[arrIdx] === sequence[seqIdx]) seqIdx++;

arrIdx++;

}

return seqIdx === sequence.length;

}

Java

• Solution 1
• Solution 2

import java.util.*;

​

class Program {

public static boolean isValidSubsequence(List<Integer> array, List<Integer> sequence) {

int arrIdx = 0;

int seqIdx = 0;

while (arrIdx < array.size() && seqIdx < sequence.size()) {

if (array.get(arrIdx) == sequence.get(seqIdx)) {

seqIdx++;

}

arrIdx++;

}

return seqIdx == sequence.size();

}

}

C++

• Solution 1
• Solution 2

using namespace std;

​

bool isValidSubsequence(vector<int> array, vector<int> sequence) {

int arrIdx = 0;

int seqIdx = 0;

while (arrIdx < array.size() && seqIdx < sequence.size()) {

if (array[arrIdx] == sequence[seqIdx])

seqIdx++;

arrIdx++;

}

return seqIdx == sequence.size();

}

---

Space-Time Complexity

	Time	Space
Worse	O(n)	O(1)

Where n is the length of the array