Arrays & Strings

Why this matters / recognition signals

Arrays and strings are the substrate almost every other pattern in this roadmap sits on top of — two pointers, sliding window, and hashing all operate over an array or string. This note covers the techniques that belong to arrays and strings themselves: in-place manipulation (reversal, rotation), prefix sums for fast range queries, and the immutability gotchas that quietly turn a linear-looking solution quadratic.

Reach for these when the problem says:

“Reverse this array/string in place” / “O(1) extra space” → two-pointer swap from both ends inward.
“Rotate the array by k” → triple-reverse trick avoids an O(n) scratch array.
“Sum of elements between index i and j” called many times → prefix sums: O(n) preprocessing, then O(1) per query.
“Build up a string in a loop” (especially in Java) → check for O(n²) naive concatenation; StringBuilder / ''.join() is the fix.
“Subarray sums to k” → prefix sum turned into a running hash-map lookup (bridges into Hashing & Hash Maps).

In-place reversal

Two pointers start at opposite ends and swap inward until they cross — the same two-pointer shape used for searching in Two Pointers & Sliding Window, here used for mutation instead.

flowchart LR
    subgraph Step0["start: [1,2,3,4,5]"]
        direction LR
        A0["1↕"] --- A1["2"] --- A2["3"] --- A3["4"] --- A4["5↕"]
    end
    Step0 -->|"swap(0,4)"| Step1
    subgraph Step1["[5,2,3,4,1]"]
        direction LR
        B0["5"] --- B1["2↕"] --- B2["3"] --- B3["4↕"] --- B4["1"]
    end
    Step1 -->|"swap(1,3)"| Step2
    subgraph Step2["[5,4,3,2,1] — left ≥ right, done"]
        direction LR
        C0["5"] --- C1["4"] --- C2["3 (mid, untouched)"] --- C3["2"] --- C4["1"]
    end

⌊n/2⌋ swaps cover the whole array — the middle element of an odd-length array never needs to move.

Rotation via the triple-reverse trick

Rotating right by k naively (shift everything by one, k times) is O(nk). Copying into a new array is O(n) time but O(n) extra space. The triple-reverse trick gets O(n) time, O(1) extra space:

Reverse the whole array.
Reverse the first k elements.
Reverse the remaining n - k elements.

Why it works: reversing the whole array puts every element in globally reversed order, but crucially it also moves the last k elements to the front (still individually reversed). Reversing each of the two segments locally un-reverses them — the segments’ internal order is restored, while their positions relative to each other stay swapped, which is exactly what a rotation is.

Worked example: rotate [1,2,3,4,5,6,7] right by k=3.

flowchart TD
    S0["[1,2,3,4,5,6,7]  original"] -->|"1. reverse all"| S1["[7,6,5,4,3,2,1]"]
    S1 -->|"2. reverse first k=3"| S2["[5,6,7,4,3,2,1]"]
    S2 -->|"3. reverse remaining n-k=4"| S3["[5,6,7,1,2,3,4]  rotated right by 3"]

Step	Operation	Array
0	start	`[1,2,3,4,5,6,7]`
1	reverse `[0, 6]`	`[7,6,5,4,3,2,1]`
2	reverse `[0, 2]` (first k)	`[5,6,7,4,3,2,1]`
3	reverse `[3, 6]` (last n-k)	`[5,6,7,1,2,3,4]`

Always compute k %= n first — a rotation by k > n is the same as by k % n, and skipping the modulo either wastes work or (worse, in a hand-rolled indexing scheme) indexes out of bounds.

Prefix sums

Given an array queried repeatedly for the sum of a range [i, j], recomputing the sum from scratch each time is O(n) per query — O(nq) total for q queries. A prefix sum array trades O(n) one-time preprocessing for O(1) per query:

prefix[0] = 0
prefix[i] = prefix[i-1] + nums[i-1]      for i = 1..n

sum(i, j) inclusive = prefix[j+1] - prefix[i]

The one-element offset (prefix is length n+1, prefix[0] = 0) exists so that sum(i, j) never needs a special case for i == 0 — subtracting prefix[0] = 0 is a no-op, so the same formula works uniformly.

Worked example: nums = [3, 1, 4, 1, 5, 9, 2], query sum(2, 5) (elements 4,1,5,9 → expect 19).

i	nums[i-1]	prefix[i]
0	—	0
1	3	3
2	1	4
3	4	8
4	1	9
5	5	14
6	9	23
7	2	25

sum(2, 5) = prefix[6] - prefix[2] = 23 - 4 = 19 ✓ — computed in one subtraction regardless of how wide the range is.

flowchart LR
    subgraph Nums["nums:  3   1   4   1   5   9   2"]
        direction LR
        N0["idx0"] --- N1["idx1"] --- N2["idx2"] --- N3["idx3"] --- N4["idx4"] --- N5["idx5"] --- N6["idx6"]
    end
    subgraph Pre["prefix: 0   3   4   8   9  14  23  25"]
        direction LR
        P0["0"] --- P1["1"] --- P2["2"] --- P3["3"] --- P4["4"] --- P5["5"] --- P6["6"] --- P7["7"]
    end
    Note["sum(2,5) = prefix[6] - prefix[2] = 23 - 4 = 19"]

Java implementations

In-place reverse and rotation

public void reverse(int[] a, int lo, int hi) {
    while (lo < hi) {
        int tmp = a[lo];
        a[lo] = a[hi];
        a[hi] = tmp;
        lo++;
        hi--;
    }
}
 
public void rotateRight(int[] nums, int k) {
    int n = nums.length;
    k %= n;                 // handle k > n
    if (k == 0) return;
    reverse(nums, 0, n - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, n - 1);
}

Prefix sums for O(1) range queries

class PrefixSum {
    private final int[] prefix;
 
    public PrefixSum(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }
 
    // inclusive range [i, j]
    public int rangeSum(int i, int j) {
        return prefix[j + 1] - prefix[i];
    }
}

String building: why StringBuilder matters

String is immutable in Java — every += in a loop allocates a brand-new String and copies the old contents into it, so a loop of n concatenations does 1 + 2 + ... + n = O(n²) total character copies.

// O(n^2) — each += allocates a new String and copies everything so far
public String badConcat(String[] words) {
    String result = "";
    for (String w : words) {
        result += w;   // full copy of `result` on every iteration
    }
    return result;
}
 
// O(n) — StringBuilder mutates an internal char buffer in place,
// amortized O(1) append (see Big-O / Complexity Analysis for why "amortized")
public String goodConcat(String[] words) {
    StringBuilder sb = new StringBuilder();
    for (String w : words) {
        sb.append(w);
    }
    return sb.toString();
}

Python implementations

In-place reverse and rotation

def reverse(a: list[int], lo: int, hi: int) -> None:
    while lo < hi:
        a[lo], a[hi] = a[hi], a[lo]
        lo += 1
        hi -= 1
 
 
def rotate_right(nums: list[int], k: int) -> None:
    n = len(nums)
    k %= n                  # handle k > n
    if k == 0:
        return
    reverse(nums, 0, n - 1)
    reverse(nums, 0, k - 1)
    reverse(nums, k, n - 1)

Prefix sums

class PrefixSum:
    def __init__(self, nums: list[int]) -> None:
        self.prefix = [0] * (len(nums) + 1)
        for i, x in enumerate(nums):
            self.prefix[i + 1] = self.prefix[i] + x
 
    def range_sum(self, i: int, j: int) -> int:
        """Inclusive range [i, j]."""
        return self.prefix[j + 1] - self.prefix[i]

String building: why `''.join()` matters

Python strings are also immutable — s += chunk in a loop can, in CPython specifically, sometimes be optimized to an in-place resize when s has a single reference, but that’s a CPython implementation detail, not a language guarantee (other implementations like PyPy don’t do it, and it silently stops applying the moment there’s a second reference to the string). The reliable, idiomatic O(n) approach is to accumulate into a list and join once:

# Fragile: relies on a CPython-specific optimization that can silently
# stop applying (e.g. under PyPy, or if `result` gets an extra reference)
def fragile_concat(words: list[str]) -> str:
    result = ""
    for w in words:
        result += w
    return result
 
 
# Reliable O(n): one allocation for the final string, list append is O(1) amortized
def reliable_concat(words: list[str]) -> str:
    parts = []
    for w in words:
        parts.append(w)
    return "".join(parts)

Complexity comparison

Technique	Time	Space	Why
Naive range sum (recompute each query)	O(n) per query	O(1)	Re-scans the range every call
Prefix sum	O(n) preprocess, O(1) per query	O(n)	One pass to build, then pure subtraction
Array rotation via extra array	O(n)	O(n)	Copies into a new array at rotated positions
Array rotation via triple reverse	O(n)	O(1)	Three passes over the same array, no extra storage
Java `String` `+=` in a loop	O(n²)	O(n) per intermediate copy	Every concat reallocates and copies the whole string so far
Java `StringBuilder.append`	O(n) amortized	O(n) buffer	Doubling internal buffer, same amortized argument as a dynamic array
Python `s += chunk` in a loop	O(n²) worst case (implementation-dependent)	O(n) per intermediate	Same immutability cost as Java, less guaranteed mitigation
Python `''.join(list)`	O(n)	O(n)	Total length known up front, one allocation

Common pitfalls

Forgetting k %= n before rotating: rotating by k > n either wastes passes (extra-array approach) or, in a hand-rolled index scheme, walks off the array entirely.
Off-by-one in prefix sum indices: sum(i, j) = prefix[j+1] - prefix[i], not prefix[j] - prefix[i] — the +1 offset exists specifically so i == 0 doesn’t need a special case; dropping it silently excludes nums[j] from every query.
Java string concatenation in a loop: the single most common “hidden O(n²)” in interview code — looks linear, isn’t. Always flag it and switch to StringBuilder before it becomes the bottleneck in a large-input test case.
Mutating an array while iterating it with a for-each: both Java’s enhanced for-loop and Python’s for x in list iterate over a live view; removing/inserting elements mid-iteration skips elements or throws ConcurrentModificationException in Java. Iterate by index backwards, or build a new collection, when removal is needed.
Confusing prefix sums with sliding window: prefix sums are for a fixed, arbitrary range queried after the fact (many random [i,j] queries); sliding window (see Two Pointers & Sliding Window) is for finding the best contiguous range under a constraint in a single pass. Reaching for prefix sums when the array also changes between queries (dynamic updates) is another mismatch — that calls for a Fenwick tree / segment tree instead, which isn’t covered by the plain prefix-sum array.
Reversing a string in Python with slicing (s[::-1]) inside a loop: correct and O(n) for one reversal, but doing it repeatedly inside a larger loop turns an otherwise-linear algorithm quadratic, same failure mode as string concatenation.

Practice problems

Rotate Array (triple-reverse trick)
Reverse String / Reverse Words in a String III
Range Sum Query — Immutable (prefix sums)
Subarray Sum Equals K (prefix sum + hash map — bridges to Hashing & Hash Maps)
Product of Array Except Self (prefix product from the left, suffix product from the right, O(1) extra space excluding output)
Valid Palindrome (two-pointer scan, character-class filtering)
Longest Common Prefix (vertical or horizontal scanning across strings)
Merge Intervals (sort + in-place merge, common array-manipulation follow-up)

Interview angles

“Can you rotate the array without extra space?” — the triple-reverse trick; be ready to prove why reversing the whole thing then reversing each half produces a rotation, not just recite the steps.
“You’re doing result += word in a loop — is that OK?” — flag Java’s O(n²) immutable-string cost unprompted and switch to StringBuilder; in Python, name the CPython-specific caveat and default to ''.join(list) as the portable answer.
“The array can be updated between queries — does your prefix sum still work?” — no; a plain prefix sum needs a full O(n) rebuild after any single update. Name the fix: a Fenwick tree (Binary Indexed Tree) or segment tree gives O(log n) update and O(log n) query instead of O(n) rebuild / O(1) query.
“How would you extend prefix sums to a 2D matrix?” — 2D prefix sum: prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1] (inclusion-exclusion to avoid double-counting the overlapping top-left region), giving O(1) rectangle-sum queries after O(rows×cols) preprocessing.
“What’s the actual amortized cost of StringBuilder.append / list append?” — O(1) amortized via the same doubling-buffer argument as a dynamic array; see Complexity Analysis for the full walk-through with real numbers.
“Is Product of Array Except Self solvable without division?” — yes, and it should be — with division, any zero in the input breaks the formula; the O(1)-extra-space (excluding output) solution multiplies a running prefix-product with a running suffix-product instead.

Notes

Explorer

Arrays & Strings

Why this matters / recognition signals

In-place reversal

Rotation via the triple-reverse trick

Prefix sums

Java implementations

In-place reverse and rotation

Prefix sums for O(1) range queries

String building: why StringBuilder matters

Python implementations

In-place reverse and rotation

Prefix sums

String building: why `''.join()` matters

Complexity comparison

Common pitfalls

Practice problems

Interview angles

My Notes

Graph View

Table of Contents

Backlinks

Notes

Explorer

Arrays & Strings

Why this matters / recognition signals

In-place reversal

Rotation via the triple-reverse trick

Prefix sums

Java implementations

In-place reverse and rotation

Prefix sums for O(1) range queries

String building: why StringBuilder matters

Python implementations

In-place reverse and rotation

Prefix sums

String building: why ''.join() matters

Complexity comparison

Common pitfalls

Practice problems

Interview angles

My Notes

Graph View

Table of Contents

Backlinks

String building: why `''.join()` matters