Array & String Foundations (Interview 150)

This module is about arrays and strings as raw memory: contiguous storage, indexed access, and in-place transformation. The patterns here look simple, but they underpin the majority of interview tasks. The goal is to make your reasoning explicit: what invariant do you maintain, and what is the exact step order that keeps it true.

Pattern 1: Read/Write Compaction ("slow/fast")

Use when you must remove elements in-place or deduplicate without extra memory.

Invariant:

• write points to the next position to fill with a valid element.
• read scans every element exactly once.

Template:

write := 0
for read := 0; read < len(nums); read++ {
    if keep(nums[read]) {
        nums[write] = nums[read]
        write++
    }
}
return write

Used by:

• Remove Element
• Remove Duplicates from Sorted Array
• Remove Duplicates from Sorted Array II

Common failures:

• Forgetting that the return value is the new length, not a new slice.
• Updating write even when the element is skipped.
• Off-by-one when the array is empty.

Pattern 2: Two Pointers from Both Ends

Use when you can place elements at the end or compare symmetric positions.

Invariant:

• Left side is "finalized" and will not change.
• Right side is "finalized" and will not change.

Template:

l, r := 0, len(nums)-1
for l <= r {
    // move l or r based on condition
}

Used by:

• Merge Sorted Array (merge from the end to avoid overwrite)
• Rotate Array (via reverse or cycle method)

Common failures:

• Overwriting values when merging from the front.
• Forgetting to reduce k with k %= n before rotation.

Pattern 3: Rotation via Reverse or Cycles

A rotation can be done in-place by reversing sections.

Reverse trick for right rotation by k:

1. Reverse the entire array.
2. Reverse the first k elements.
3. Reverse the remaining n-k elements.

Why it works: the rightmost k elements move to the front, and their internal order is restored by the second reverse.

Used by:

• Rotate Array

Common failures:

• Forgetting k %= n.
• Reversing in the wrong order.

Pattern 4: Single-Pass Greedy Scans

Some array problems are solved by scanning once while maintaining a best-so-far state.

Examples:

• Best Time to Buy and Sell Stock: track the minimum price so far and compute max profit.
• Jump Game: track the farthest reachable index and fail if i > farthest.

Invariant:

• The tracked state always reflects the best possible result using elements up to i.

Common failures:

• Updating the state in the wrong order (e.g., updating min before using it).
• Returning too early without checking reachability.

Pattern 5: Counting and Selection

When you need a majority element or index-based selection, counts or buckets usually beat sorting.

Majority (Boyer-Moore):

• Maintain a candidate and a count.
• If count == 0, pick new candidate.
• Increment or decrement based on equality.

H-Index:

• Sorting works, but a bucket count also works in O(n).

Common failures:

• Forgetting that Boyer-Moore assumes a true majority exists.
• Off-by-one in H-index comparisons.

Pattern 6: Prefix/Suffix Products

When the output at index i needs all elements except i, compute prefix and suffix products.

Invariant:

• prefix[i] is the product of all elements before i.
• suffix[i] is the product of all elements after i.

Used by:

• Product of Array Except Self

Quick checks (when to use this module's patterns)

• In-place edits required? Use read/write compaction or two pointers.
• Need to move a block? Try reverse-based rotation.
• Find max/min under a constraint? Try a single-pass greedy scan.
• Exclude current element from aggregate? Try prefix/suffix.

Common pitfalls across the module

• Off-by-one errors at the ends of the array.
• Forgetting to handle len == 0 or k %= n.
• Mutating the input but still returning a new slice.
• Hidden O(n^2) behavior (nested loops) on large arrays.

Problems in this module

• Merge Sorted Array
• Remove Element
• Remove Duplicates from Sorted Array
• Remove Duplicates from Sorted Array II
• Majority Element
• Rotate Array
• Best Time to Buy and Sell Stock
• Best Time to Buy and Sell Stock II
• Jump Game
• Jump Game II
• H-Index
• Product of Array Except Self
• Gas Station