Arrays and Strings

Every movement needs a reason

Suppose an interviewer gives you a sorted array and asks whether two values sum to a target. You place one pointer at each end. The sum is too small, so you move the left pointer.

Why that pointer?

“Because this is two pointers” names a pattern but does not answer the question. The answer comes from what sorted order permits you to discard. If the smallest remaining value paired with the largest is still too small, pairing that smallest value with anything else cannot work. Advancing the left pointer rejects no viable pair. The movement is the proof.

Arrays and strings make this habit unusually visible. Their algorithms tend to move boundaries, summarize completed regions, or reuse storage. At each step, some part of the input becomes safe to forget. The central question is:

What fact lets this algorithm stop reconsidering the positions it has left behind?

Sometimes the fact is sorted order. Sometimes it is a valid window, prefix algebra, a finalized output region, or a shrinking unknown zone. When no such fact exists, the familiar pattern is usually the wrong one.

Two pointers discard candidates

Two pointers are useful when one comparison makes a whole set of future comparisons unnecessary. Sorted pair search is the cleanest example:

def has_pair_with_sum(values, target):
    left = 0
    right = len(values) - 1

    while left < right:
        total = values[left] + values[right]
        if total == target:
            return True
        if total < target:
            left += 1
        else:
            right -= 1

    return False

When total < target, decreasing right can only make the sum smaller, so values[left] cannot participate in an answer. The other movement follows by the symmetric argument. The loop uses left < right because one element may not pair with itself.

The same proof takes different forms elsewhere:

• In a palindrome check, a confirmed matching pair no longer matters, so both pointers move inward.
• In a merge, the smaller front value is the next final output value, so only its source pointer advances.
• In stable compaction, a read pointer explores input while a write pointer marks the end of the final output prefix.
• In a merge into spare capacity, writing from the back prevents the output from overwriting values that have not yet been read.

These are not interchangeable tricks. Sorted two-sum relies on order. A read/write compaction relies on region ownership. A palindrome may also need a decision about whether the unit of comparison is a byte, code point, or normalized character. Two indexes alone establish nothing.

Before coding, say what a movement eliminates. The useful tests then become obvious: one element, duplicate values such as [3, 3], an answer at the two outer positions, and a contract that asks for original indexes even though sorting would change them.

A window carries the exact state of a segment

A sliding window is not merely two pointers moving in the same direction. It maintains state for one contiguous segment. The right boundary admits a new item; the left boundary removes items until the segment again satisfies the condition under which answers may be recorded.

The usual variable-size shape is:

left = 0
state = empty

for right in input:
    add input[right] to state
    while the segment is invalid:
        remove input[left] from state
        left += 1
    record an answer from [left, right]

Every word in the invariant matters: state must describe exactly the items from left through right, and the answer must be recorded only after validity has been restored.

Consider the longest substring without repeated characters:

def length_of_longest_unique_substring(text):
    last_seen = {}
    left = 0
    best = 0

    for right, char in enumerate(text):
        if char in last_seen and last_seen[char] >= left:
            left = last_seen[char] + 1
        last_seen[char] = right
        best = max(best, right - left + 1)

    return best

"abba" is the revealing input. When the final a arrives, its previous position lies outside the active window "ba". Assigning left = last_seen["a"] + 1 without the >= left guard would move left backward and admit the repeated b. The guard is the proof that discarded positions stay discarded.

Other windows keep counts rather than last positions. If a count reaches zero while the window shrinks, deleting that key may be essential: a map containing three keys with one zero count does not represent “three active characters.”

Most importantly, the condition must support directional repair. With positive numbers, expanding a sum window cannot reduce its sum, and shrinking cannot increase it. With arbitrary integers, those claims fail. A negative number can make either boundary move surprising. “Contiguous” is not enough to justify a window.

Prefixes replace movement with algebra

When no safe boundary movement exists, a summary of completed positions may do the work instead. A prefix sum stores the value before each index:

prefix[0] = 0
prefix[i + 1] = prefix[i] + values[i]

sum(values[left:right]) = prefix[right] - prefix[left]

The leading zero is not decoration. It makes a range beginning at index zero obey the same subtraction rule as every other range. Choosing half-open ranges also keeps the meaning stable: prefix[i] always summarizes values strictly before i.

Now return to a prompt that tempts people into the wrong window:

Count the contiguous subarrays whose sum is k. Values may be positive, zero, or negative.

At a position with running prefix sum running, a subarray ending here has sum k when an earlier prefix was running - k. Several earlier positions may have that value, so the algorithm must remember a count, not membership:

def count_subarrays_with_sum(values, k):
    count_by_prefix = {0: 1}
    running = 0
    answer = 0

    for value in values:
        running += value
        answer += count_by_prefix.get(running - k, 0)
        count_by_prefix[running] = count_by_prefix.get(running, 0) + 1

    return answer

For [1, -1, 1] and k = 1, the answer is three. Negatives defeat the window’s direction, while duplicate prefix sums create several valid starting points. For [0, 0, 0] and k = 0, the answer is six; a set would collapse the evidence needed to count them.

The cost is expected O(n) time and O(n) additional space under ordinary hash table assumptions. In a fixed-width integer language, the prefix type must also be wide enough for the accumulated sum.

Difference arrays postpone repeated updates

Prefix sums make repeated range reads cheap. Difference arrays apply the same boundary idea to repeated range writes.

To add delta to every position in the inclusive range [left, right], record where the effect begins and where it ceases:

diff[left] += delta
if right + 1 < n:
    diff[right + 1] -= delta

A later prefix pass reconstructs the active change at every position:

running = 0
for i in 0..n-1:
    running += diff[i]
    result[i] = original[i] + running

During reconstruction, running is the sum of all updates active at i. That statement explains both endpoint writes. It also exposes the likely bug: forgetting the stop event at right + 1 lets an update leak through the rest of the array.

Dense arrays make sense for flight seats or bounded indexes. For a huge sparse timeline, store deltas only at event coordinates, sort those coordinates, and scan them. Allocating up to the largest timestamp would preserve the formula while missing the engineering problem.

In-place work is an ownership proof

“O(1) extra space” does not explain why mutation is safe. An in-place algorithm needs a map of which positions are final, unread, and available as scratch.

Stable compaction has a particularly useful invariant:

write = 0
for read in 0..n-1:
    if values[read] should remain:
        values[write] = values[read]
        write += 1
return write

Before each iteration, values[0:write] is the final compacted form of the input already examined, values[read:] is unread, and the positions between them may be overwritten. The returned length is part of the contract; values beyond it are usually unspecified.

Merging two sorted arrays into spare capacity in the first array reverses the direction of ownership. The largest remaining value belongs at the last free position. Writing backward makes the suffix final without destroying the initialized prefix that remains to be read. Writing forward requires shifting or extra storage.

Strings add a language-level constraint. In a language with immutable strings, repeated concatenation or slicing is allocation, even if the algorithm uses only two integer variables. Be precise about auxiliary storage and about the caller’s permission to mutate input.

Matrices require explicit geometry

An array index has one boundary pair. A matrix adds another, and vague names start producing transposed coordinates and square-only solutions. Establish the contract first: (row, column), row-major access, the dimensions, and whether neighbors are four-directional or include diagonals.

For a rectangular matrix:

rows = len(matrix)
cols = len(matrix[0]) if rows else 0

for row in 0..rows-1:
    for col in 0..cols-1:
        for (dr, dc) in [(1,0), (-1,0), (0,1), (0,-1)]:
            next_row = row + dr
            next_col = col + dc
            if 0 <= next_row < rows and 0 <= next_col < cols:
                process(next_row, next_col)

The empty check must precede matrix[0]. A 2 x 3 test exposes code that silently exchanges rows and columns.

Spiral traversal uses geometry rather than neighbors. Four bounds enclose the unread rectangle. After emitting the top row and right column, emit the bottom row only if a different row remains, and the left column only if a different column remains. Those guards prevent a one-row or one-column center from being read twice. The invariant is visual: everything outside top..bottom and left..right is final.

Partitioning shrinks the unknown zone

Partitioning also reasons in regions, but it does not usually preserve order. In the three-way form, four zones make the proof:

low = 0
mid = 0
high = n - 1

while mid <= high:
    if values[mid] belongs in the low category:
        swap values[low], values[mid]
        low += 1
        mid += 1
    elif values[mid] belongs in the middle category:
        mid += 1
    else:
        swap values[mid], values[high]
        high -= 1

Before each iteration, positions before low are low, low..mid-1 are middle, mid..high are unknown, and positions after high are high. When a high value is swapped out of mid, the incoming value is still unknown. That is why mid does not advance in the final branch.

The prompt must decide whether this reordering is acceptable. A stable partition is a different contract and commonly costs extra space or movement. Quickselect adds another qualification: its familiar linear running time is expected under a suitable pivot strategy; poor pivots can produce quadratic work.

For strings, settle contiguity and the unit

Two questions precede the pattern choice for string problems.

First, must the characters be contiguous? A substring includes everything between two boundaries, so windows, prefix-like summaries, rolling hashes, or center expansion may apply. A subsequence preserves order but permits gaps, so progress is usually a match index or dynamic-programming state:

def is_subsequence(pattern, text):
    matched = 0

    for char in text:
        if matched < len(pattern) and pattern[matched] == char:
            matched += 1

    return matched == len(pattern)

Here matched means that the first matched characters of pattern have already appeared in order. No window can express that permission to skip.

Second, what counts as one character? Depending on the contract and language, byte indexes, Unicode code points, and user-visible grapheme clusters can differ. Case folding and normalization can change equality and even length. Do not pay for full text normalization when the prompt grants lowercase ASCII; do not assume ASCII when it does not.

This distinction also changes complexity claims. Constructing every substring may copy O(n) characters for each of O(n²) ranges. An algorithm described as “two loops” can therefore perform O(n³) character work.

Rehearse the reason, not the label

For a new problem, resist naming the pattern until you can finish one of these sentences:

• “This pointer may advance because every candidate it leaves behind is impossible by …”
• “This window may shrink because removing from the left restores …”
• “This range equals the difference between summaries at …”
• “This update is active after one endpoint and inactive after …”
• “This write is safe because the unread region begins at …”
• “This matrix or partition boundary encloses exactly the positions that are still …”

Then try one hostile case against the sentence, not five generic edge cases. Use "abba" against a last-seen window; negatives against a sum window; a range beginning at zero against prefix indexing; an update ending at the last position against difference bounds; a one-row matrix against spiral traversal; and a high-category value swapped into mid against three-way partitioning.

The pattern atlas is not a catalog of shapes to recognize on sight. It is a catalog of reasons work does not need to be repeated. Name the state, say what has become final, and make the next movement earn its safety. The next chapter adds hash maps and sets, which let an algorithm remember facts that position alone cannot recover.

Related reading

• Chapter 31: Complexity and Constraint Analysis
• Chapter 33: Correctness Before Cleverness
• Chapter 34: Writing Senior-Level Interview Code
• Chapter 38: Complete Annotated Coding Interviews
• Chapter 40: Hash Maps and Sets