Subsequence

Unit 2 Session A

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Will either list ever be empty?
  • Potentially, yes. Your code should allow for this.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Take turns looking for each element of the smaller list, in order, until we either find all elements or run out of room to search.

1) First, make a variable to keep track of our current sequence entry
2) Initialize the sequence_index variable to 0
3) Loop through the number array, and each time:
  a) If sequence_index is invalid, we've found everything, return True
  b) If sequence_index is valid, compare the value at sequence_index to
     the current loop value
       i) If it matches, we can increment sequence_index by 1
4) If the loop finishes, we ran out of numbers, so return False

I-mplement

def is_subsequence(array, sequence):
    seq_idx = 0
    for num in array:
        if seq_idx == len(sequence):
            return True
        if sequence[seq_idx] == num:
            seq_idx += 1
    return False