Understanding the Simultaneous Traversal Pattern

When One Array Isn’t Enough

Every pattern we’ve covered so far works on a single array. But some problems give you two arrays and ask you to do something that requires looking at both at the same time.

Merging two sorted lists. Checking if one sequence appears inside another. Finding common elements between two arrays. These problems can’t be solved by finishing one array and then starting the other — the answer depends on how items in both arrays relate to each other at each step.

The simultaneous traversal pattern handles exactly this: traverse two arrays in a single pass using two index variables, where a condition at each step decides which index moves forward.

The Mental Model

Think of two conveyor belts running side by side. Each belt carries items in order. You have one hand on each belt. At every moment:

• You compare the items both hands are holding.
• Based on the comparison, you pick from the left belt, the right belt, or both.
• You advance whichever belt(s) you took from.

Neither belt ever rewinds. You just decide, at each step, which hand moves forward.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  subgraph ARR1["arr1  (size N)"]
    direction LR
    A0["a₀"] --- A1["a₁"] --- A2["a₂"] --- A3["a₃"] --- A4["..."]
  end
  subgraph ARR2["arr2  (size M)"]
    direction LR
    B0["b₀"] --- B1["b₁"] --- B2["b₂"] --- B3["..."]
  end
  I1(["index1"]) --> A0
  I2(["index2"]) --> B0

Two index variables — one per array — start at position 0 and move independently based on a condition evaluated at each step.

Two Index Variables, One Loop

The implementation has a fixed shape regardless of the problem:

• index1 tracks the current position in arr1
• index2 tracks the current position in arr2
• The main loop runs while both arrays have unprocessed elements
• After the main loop, two cleanup loops handle whatever remains in either array

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Start(["index1=0, index2=0"])
  Check{"index1 < len(arr1)<br/>AND<br/>index2 < len(arr2)"}
  Cond{"condition"}
  Adv1["advance index1"]
  Adv2["advance index2"]
  AdvBoth["advance both"]
  Tail1{"index1 < len(arr1)?"}
  Tail2{"index2 < len(arr2)?"}
  Finish1["process remaining arr1"]
  Finish2["process remaining arr2"]
  Done(["done"])

  Start --> Check
  Check -->|"yes"| Cond
  Check -->|"no"| Tail1
  Cond -->|"only arr1"| Adv1 --> Check
  Cond -->|"only arr2"| Adv2 --> Check
  Cond -->|"both"| AdvBoth --> Check
  Tail1 -->|"yes"| Finish1 --> Tail2
  Tail1 -->|"no"| Tail2
  Tail2 -->|"yes"| Finish2 --> Done
  Tail2 -->|"no"| Done

Simultaneous traversal flow — the main loop runs while both arrays have items; two cleanup loops drain whichever array still has leftover elements.

The cleanup loops are what separate simultaneous traversal from the two-pointer pattern. Two pointers stop when the pointers converge on a single array. Simultaneous traversal continues until both arrays are fully processed.

The Template

from typing import List

def simultaneous_traversal(arr1: List[int], arr2: List[int]) -> None:
    index1 = 0  # Current position in arr1
    index2 = 0  # Current position in arr2

    # Main loop: run while both arrays have unprocessed elements.
    # At each step, the condition decides which index advances.
    while index1 < len(arr1) and index2 < len(arr2):

        if should_advance_arr1(arr1[index1], arr2[index2]):
            # process arr1[index1]
            index1 += 1  # Move arr1 forward

        if should_advance_arr2(arr1[index1], arr2[index2]):
            # process arr2[index2]
            index2 += 1  # Move arr2 forward

    # arr2 exhausted first — process any remaining elements in arr1
    while index1 < len(arr1):
        # process arr1[index1]
        index1 += 1

    # arr1 exhausted first — process any remaining elements in arr2
    while index2 < len(arr2):
        # process arr2[index2]
        index2 += 1

How Pointer Movement Works

At each step, exactly one of three outcomes happens, driven by the condition:

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  C{"Compare<br/>arr1[index1]<br/>vs<br/>arr2[index2]"}
  C -->|"arr1[i1] < arr2[i2]"| R1["index1++<br/>(process arr1[i1])"]
  C -->|"arr1[i1] > arr2[i2]"| R2["index2++<br/>(process arr2[i2])"]
  C -->|"arr1[i1] == arr2[i2]"| R3["index1++ AND index2++<br/>(process both)"]

The condition evaluated each step determines which pointer advances — one, the other, or both. No pointer ever moves backwards.

The condition is problem-specific. Some examples:

Why Cleanup Loops Are Needed

When the main loop exits, exactly one of these is true:

• index1 == len(arr1) — arr1 is exhausted, but arr2 may still have items
• index2 == len(arr2) — arr2 is exhausted, but arr1 may still have items

Those remaining items are often meaningful. In a merge, they need to be appended to the result. In a subsequence check, if s still has characters left when t runs out, the answer is false.

The cleanup loops guarantee that no element in either array is silently skipped.

Complexity

Every element in both arrays is processed exactly once — each index moves forward and never backwards. If arr1 has N elements and arr2 has M:

Why brute force is O(N × M): A naive nested loop resets index2 to 0 for each element in arr1. That means every element of arr1 triggers a full scan of arr2. Simultaneous traversal eliminates the reset — index2 only ever moves forward.