Arrays & Traversal

The one pass that replaces the nested loop.

The idea

An array gives you two things in constant time: the element at an index, and the length. Almost every array technique is about turning a problem that looks like it needs to compare everything with everything into one that needs a single walk.

The tell is a nested loop where the inner one is doing bookkeeping rather than real work — counting, searching for a partner, tracking a running best. That inner loop is usually replaceable by state you carry along.

// O(n^2): the inner loop re-derives what you already passed
for i in range(n):
    for j in range(i):
        ...

// O(n): carry the answer with you
running = initial
for i in range(n):
    running = combine(running, a[i])

The three shapes worth recognising: a running aggregate (prefix sums, max so far), a decision per element (extend or restart, as in Kadane's), and two indices moving independently — which is its own topic.

Walkthrough

A single pass carrying a running total — watch the write follow the read one step behind.

What it costs

time: O(n) for a single pass
space: O(1) if you carry state, O(n) if you build an output array

Nested loops over the same array are the signal. The question to ask is what the inner loop actually needs — often it is one number you could have been tracking all along.

When to reach for it

You need any element by position in constant time — the one thing only an array gives you.
You are scanning in order, where contiguous memory makes it far faster in practice than the notation suggests.
The size is known, or grows only at the end.
You need the data laid out for a two-pointer, sliding-window, or binary-search technique.

Rather than the obvious alternative

A linked list

A list only wins when you insert and remove in the middle constantly. An array beats it on nearly everything else, including scans, because its elements sit together in memory.

A hash map

If your keys are already 0..n-1, an array is a hash map with no hashing, no collisions and no overhead. Reach for the map only when the keys are sparse or not integers.

How to spot it

You wrote a nested loop and the inner one only searches or counts.
The problem says 'contiguous' or 'subarray'.
You need a running total, running maximum, or a comparison against everything seen so far.
The naive solution is O(n^2) and the input size suggests that will not pass.

Where it goes wrong

Reading past the end

`a[a.length]` is undefined in JavaScript and an IndexError in Python. Loop conditions using `<=` are the usual cause.

Mutating while iterating

Removing elements during a forward loop shifts everything after the removal, so the next element is skipped. Build a new array or walk backwards.

Assuming non-empty

An empty array breaks `a[0]` and any 'best so far' seeded from the first element. Decide what the answer is for an empty input before you write the loop.

Practise it

Build it

The problems above are one function each. These assemble the same ideas into a working thing across several files.