The Simultaneous Traversal Pattern: Checking if One Array Is a Subsequence of Another

What "simultaneous traversal" means

Imagine you have two lists and you want to walk through both of them at the same time. At each step you look at one item from each list, apply some simple test, and then decide how to move forward: sometimes you step forward in both lists, and sometimes you step forward in only one. This idea of "walk through more than one array together, and move based on what you find" is called the simultaneous traversal technique.

It works best on a small family of (usually easy) problems that share one shape:

> Template: Given two arrays, traverse both at once based on the result of some function applied to items from both arrays.

Most of these problems use exactly two arrays, but some can use more.

The example problem: is s a subsequence of t?

We are given two arrays (here, arrays of characters):

• s = a, b, c
• t = h, a, e, b, h, c, f

We must answer: is s a subsequence of t?

A *subsequence* means: can we find all the letters of s inside t, in the same order, without rearranging them? The letters do not need to be next to each other in t — other letters may sit between them. We just need a, then later a b, then later a c.

Looking at t, the a is at position 1, a b is at position 3, and a c is at position 5. They appear in the right order, so the answer is True. (The skipped letters h, e, h, f simply don't matter.)

First idea: the brute-force solution

The most natural first attempt is to handle one letter of s at a time:

1. Pick the first item in s (here a).
2. Walk through t from the start until you find that item.
3. Pick the next item in s (b), and keep walking through t from where you stopped — never restart from the beginning.
4. Repeat. If you manage to find every item of s this way, return true. If you run off the end of t while letters of s still remain, return false.

In code, this uses an outer loop over s and an inner loop that scans t:

bool isSubsequence(vector<char>& s, vector<char>& t) {
    int j = 0;
    // Traverse each element of array `s`
    for(int i=0; i<s.size(); i++) {
        if(j == t.size()) {
            return false;
        }
        // Store current element of `s`
        char item = s[i];
        // Traverse `t` and look for `item` in `t`
        while (j < t.size()) {
            if(item == t[j]) {
                j++;
                break;
            }
            j++;
        }
    }
}

Notice that j (the position in t) is declared outside the loops, so each search for the next letter continues from where the last one ended. This actually already walks through both arrays together — but with a loop inside a loop, an item variable, and a break, it is fiddly and easy to get wrong.

A cleaner idea: the simultaneous traversal solution

The same problem fits our template neatly, and the result is much simpler. Keep one pointer in each array:

• index1 → current position in s
• index2 → current position in t

Now apply one rule on every step:

> Compare s[index1] and t[index2].

> - If they match, move forward in both arrays (index1++ and index2++) — we found this letter, so look for the next one.

> - If they don't match, move forward in only t (index2++) — keep searching t for the current letter of s.

Walking through s = a,b,c and t = h,a,b,e,h,c,f:

• a vs h → no match → move only in t
• a vs a → match → move in both
• b vs b → match → move in both
• c vs e → no match → move only in t
• c vs h → no match → move only in t
• c vs c → match → move in both

Now index1 has gone past the end of s. s is fully traversed, so s is a subsequence of t → True.

// pointer for s
int index1 = 0;
// pointer for t
int index2 = 0;
while (index1 < s.length() && index2 < t.length()) {
    if (s[index1] == t[index2]) {
        // If the current character matches, move the pointer for s
        index1++;
    }
    // Move the pointer for t in every iteration
    index2++;
}

The loop stops when either pointer reaches the end. If index1 reached the end of s, every letter was found and the answer is true; otherwise t ran out first and the answer is false.

This version does exactly the same work as the brute-force version, but it is cleaner, easier to read, and less error-prone — no inner loop, no break, no temporary item.

Why this matters and where to use it

The lesson is not really about subsequences — it's about recognizing a *pattern*. Whenever a problem says "given two (or more) arrays, compare items and step through them based on the result," reach for simultaneous traversal. Other easy problems that fit the same shape include:

• Subsequence checker (the one above)
• Merge sorted arrays
• Unique intersections
• Repeated intersections

Once you can spot the pattern, all of these become small variations on "two pointers, one comparison, move one or both."