Array Traversal and Pattern Recognition

What is this?

Imagine watching a hiking trail go by and trying to answer "was that a steady uphill?" or "where was the highest peak?" You don't need to walk the trail twice — you just pay attention as you go, remembering one or two small things, like "am I still climbing?" or "how long has this ride lasted?" This chapter is about reading an array in a single walk while carrying just enough memory to spot the shape you care about, instead of clumsily checking everything against everything.

💡 Fun fact: This one-pass, "advance the smallest pointer" merge is the same trick databases use to combine sorted lists when answering a search — and it dates back to John von Neumann, who described merge sort in 1945, making it one of the very first algorithms ever written for a stored-program computer.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: most "does this array have property X?" questions don't need sorting, nesting, or extra memory — just one disciplined left-to-right sweep that carries a little state (a flag, a counter, or a set of cooperating pointers). Learn to choose the right state to carry, and a whole family of pattern problems collapses into a single O(n) pass.

1. What "traversal & pattern recognition" really means

A traversal problem asks you to recognize a shape in a sequence — a consistent direction (monotonic), a rise-then-fall (mountain), a value shared across several streams (intersection). The naive instinct is to re-scan: compare every pair, test every subarray, rebuild a set. The skill this chapter teaches is to carry exactly enough state as you walk so each element is examined a constant number of times.

Three kinds of state cover most of it:

 1) a FLAG        — "is this still possible?"      e.g. inc? / dec?
 2) a COUNTER     — "how long is the current run?"  e.g. up / down length
 3) COOP POINTERS — multiple read-heads in lockstep e.g. merge of sorted inputs

The unifying move: never walk backward. If you find yourself re-scanning something you already passed, there's usually a piece of state that would have remembered it for you.

⚠️ The beginner trap is nested re-scanning — an O(n²)/O(n³) "check every subarray" or "membership-test every element." Almost always, one pass with the right carried state replaces it with O(n).

2. Where you'll actually meet this

Single-pass pattern checks are real validation and detection primitives:

• Distributed systems. Asserting monotonic invariants (Lamport clocks, Kafka offsets, Raft log indices) is a monotonicity scan; intersecting replicas' sorted committed-key lists is a multi-pointer merge; spotting a load surge for autoscaling is a rise-then-fall scan.
• Search & databases. Conjunctive query evaluation intersects sorted posting lists; sort-merge joins walk sorted inputs in lockstep — both are coordinated multi-pointer sweeps.
• Observability / SRE. Spike and trend detection over latency/error/throughput time series — mountains, plateaus, monotone climbs.
• Networking. TCP sequence numbers advancing monotonically; congestion-window burst envelopes rising then backing off.
• Finance / retail. Validating cumulative series move one direction; symbols or SKUs common to several sorted feeds.

If a problem says is it sorted/monotonic, find the peak/valley, longest run of …, common to all, in one pass — this chapter's toolkit applies.

3. The traversal toolkit (patterns to recognise)

1. Optimistic flags. Assume every possibility is true; let the scan falsify them. The answer is "did any survive?" (monotonic = inc or dec). O(1) space, one pass.
2. Running-length counters. Track the length of the current run (ascent, descent, equal-streak). A completed shape is read straight off the counters (mountain = up + down + 1); a break resets them, auto-segmenting the array.
3. Cooperating pointers on sorted inputs. Multiple read-heads advancing the smallest value in lockstep — a merge. Finds intersections/joins in O(total) time, O(1) space, output already ordered.
4. Exploit structure. Sorted? Then verify, don't sort; merge, don't hash. Strict vs non-strict comparisons (< vs ≤) are the whole game in shape problems — get them right.
5. Guard the edges. Empty, single-element, all-equal, and boundary positions (a peak can't sit at index 0 or n-1) decide correctness more than the main loop.

4. A 30-second worked example (carry a counter)

Longest rise-then-fall in [1, 3, 5, 4, 2], in one pass with up/down counters:

One walk, two counters, no nested loop — the work you already did is the measurement. That carried-state reflex recurs across every problem in this chapter.

5. Problems in this chapter

▶ Find Common Elements in Three Sorted Arrays

Intersect three sorted streams (think: keys committed on all three replicas) with three pointers, advance-the-smallest — O(total) time, O(1) space, no hash set.
Pattern: cooperating pointers / merge. Target: O(n₁+n₂+n₃), O(1).

▶ Longest Mountain Subarray

Find the longest strict rise-then-fall run (a clean load/latency surge). One pass carrying up/down run lengths; a flat or new climb resets them.
Pattern: running-length counters / state machine. Target: O(n), O(1).

▶ Check if Array is Monotonic

Decide if a series never changes direction (a monotonic counter/clock). One pass with two optimistic flags, inc and dec; the array is monotonic iff one survives.
Pattern: optimistic flags. Target: O(n), O(1).

6. Common pitfalls 🚫

• Nested re-scanning — "check every subarray" / "membership-test every element" is O(n²)+; carry state and sweep once instead.
• Sorting when you only need to verify — verifying an order is O(n); re-sorting already-sorted inputs throws the gift away.
• Strict vs non-strict mix-ups — a plateau (==) breaks a strict mountain but is fine for a non-strict monotonic check. Pick the comparison deliberately.
• Forgetting to reset counters — back-to-back shapes (two mountains, a new run) need the running state cleared at the break.
• Edge neglect — empty, single, all-equal, and "peak can't be at the boundary" are where these problems are actually won or lost.

7. Key takeaways

1. One sweep + the right carried state replaces nested re-scanning — flags, counters, or cooperating pointers, chosen to fit the shape.
2. Optimistic flags answer "is property X still possible?"; running-length counters measure the current run and reset at breaks; multi-pointers merge sorted inputs.
3. Never walk backward — if you're re-scanning, some state would have remembered it for you.
4. Exploit sortedness: verify instead of sort, merge instead of hash — O(n)/O(1) instead of O(n log n)/O(n).
5. The same three reflexes power production code — monotonic-invariant asserts, posting-list/replica intersection, and surge detection — which is why interviewers lean on this family.