Skip to content
Hari KharelStudy

Arrays and in-place manipulation

coreCommon atGoogleMetaAmazonMicrosoftAppleRead firstComplexity analysisPractise in the Sandbox →

An array is a block of equal-sized slots side by side in memory, so a[i] is one multiplication away: O(1). Appending to a dynamic array is O(1) amortized; inserting or deleting in the middle is O(n) because everything after it shifts. In-place techniques (a read pointer and a write pointer, swaps, reversals) rearrange an array with O(1) extra space.

The idea in plain words

Section titled “The idea in plain words”

Picture a row of numbered lockers, all the same width. To reach locker 700 you don’t walk past 699 others: you compute start + 700 × width and go there. That’s why indexing is constant time, and why scanning left to right is the fastest loop a CPU runs (each memory fetch brings the next few slots along for free).

The price is rigidity:

  • Inserting in the middle means sliding every later locker’s contents one step to make room. O(n).
  • Growing means the block may not have room to extend, so a dynamic array (Python list, JS Array, C# List<T>) allocates a bigger block and copies everything across. Done right, that copy is rare enough to average out to O(1) per append.

In-place means you rearrange the data using the array itself as your workspace, with only a few index variables on the side. Interviewers love it because it forces you to keep a precise invariant about which part of the array means what.

See it

Section titled “See it”

The most reusable in-place pattern: r reads every element, w marks where the next kept element goes. Everything left of w is finished output. Change the values or the number to remove.

Read pointer, write pointer
step through
w
3
2
2
3
4
2
5
2
01234567
r
r0
w0
kept[]
kept prefix a[0..w-1]copied fromskippedleftover
Remove every 2 in place, keeping the order of the rest. Invariant: a[0..w-1] holds exactly the kept values seen so far.
1 / 10

When to reach for it

Section titled “When to reach for it”
The problem says… Why this fits
“in place”, “O(1) extra space”, “modify the input” Read/write pointers or swaps use the array as its own buffer.
“remove / filter / dedupe while keeping order” Read/write compaction: one pass, stable.
“partition”, “move all X to the end”, “group into three kinds” Swap-based partitioning (Lomuto, Hoare, Dutch flag).
“rotate / reverse / rearrange” Reversals and cyclic swaps, O(1) space.
index arithmetic: “position i maps to…”, values in 1..n The array can be its own hash table (mark visited by sign or by swapping into place).
random access by position, fixed size A plain array beats any linked structure.

How it works

Section titled “How it works”

Read/write compaction

Section titled “Read/write compaction”
  1. Set w = 0. Invariant: a[0..w-1] is the output so far.
  2. Move r across every element.
  3. If a[r] should be kept, copy it to a[w] and advance w. Otherwise skip it.
  4. Return w as the new length. In a fixed-size array the tail is garbage; in Python/JS you can truncate.
remove_all / reverse_range.py
def remove_all(a: list[int], val: int) -> int:
    """Remove every `val` in place, keeping order. Returns the new length w; a[:w] is the result."""
    w = 0  # 1. invariant: a[0:w] holds the kept values seen so far
    for r in range(len(a)):  # 2. r reads every element exactly once
        if a[r] != val:
            a[w] = a[r]  # 3. keep it: copy down into the first free slot
            w += 1
    return w




def reverse_range(a: list[int], lo: int, hi: int) -> None:
    """Reverse a[lo..hi] (inclusive) in place with two pointers meeting in the middle."""
    while lo < hi:
        a[lo], a[hi] = a[hi], a[lo]
        lo += 1
        hi -= 1




if __name__ == "__main__":
    a = [3, 2, 2, 3, 4, 2, 5, 2]
    w = remove_all(a, 2)
    del a[w:]  # 4. Python lists can shrink; in fixed arrays you just return w
    assert a == [3, 3, 4, 5]
    assert remove_all([], 1) == 0
    b = [1, 2, 3, 4, 5]
    reverse_range(b, 1, 3)
    assert b == [1, 4, 3, 2, 5]
    print("ok")

Three zones with swaps (Dutch national flag)

Section titled “Three zones with swaps (Dutch national flag)”

Dijkstra’s problem: sort an array of three kinds of values in one pass. Keep three boundaries and an “unknown” zone that shrinks by one each step.

  1. lo = end of the “less” zone, mid = next unknown, hi = start of the “greater” zone (from the right).
  2. If a[mid] is small, swap it into the left zone; advance lo and mid.
  3. If it’s big, swap it with a[hi] and shrink hi. Don’t advance mid: the value you just pulled in hasn’t been looked at.
  4. If it’s equal, just advance mid.
three_way_partition.py
def three_way_partition(a: list[int], pivot: int) -> None:
    """Rearrange in place into [< pivot | == pivot | > pivot] in one pass (Dijkstra's Dutch flag)."""
    lo, mid, hi = 0, 0, len(a) - 1
    # 1. invariant: a[:lo] < pivot, a[lo:mid] == pivot, a[mid:hi+1] unknown, a[hi+1:] > pivot
    while mid <= hi:
        if a[mid] < pivot:
            a[lo], a[mid] = a[mid], a[lo]  # 2. small: swap into the left zone, both advance
            lo += 1
            mid += 1
        elif a[mid] > pivot:
            a[mid], a[hi] = a[hi], a[mid]  # 3. big: swap to the right; don't advance mid,
            hi -= 1  #    the value that came back is still unknown
        else:
            mid += 1  # 4. equal: already in the middle zone




if __name__ == "__main__":
    a = [2, 0, 2, 1, 1, 0]
    three_way_partition(a, 1)
    assert a == [0, 0, 1, 1, 2, 2]
    b = [5, 1, 9, 5, 3, 7, 5]
    three_way_partition(b, 5)
    assert all(x < 5 for x in b[:2]) and b[2:5] == [5, 5, 5] and all(x > 5 for x in b[5:])
    empty: list[int] = []
    three_way_partition(empty, 0)
    print("ok")

Arrays in each language

Section titled “Arrays in each language”
Python TypeScript / JS C#
dynamic array list Array (T[]) List<T>
fixed array array.array, NumPy typed arrays (Int32Array), fixed length T[] (fixed length)
growth when full ≈ ×1.125 plus a constant V8: ≈ ×1.5 plus 16 ×2 (starts at 4)
slice a[i:j] copies slice copies a[i..j] on arrays copies; AsSpan(i, len) is a view
insert/remove at front insert(0,x) / pop(0): O(n) unshift / shift: O(n) Insert(0,x) / RemoveAt(0): O(n)
swap a[i], a[j] = a[j], a[i] [a[i], a[j]] = [a[j], a[i]] (a[i], a[j]) = (a[j], a[i])

What it costs

Section titled “What it costs”
Operation Cost Why
a[i] read / write O(1) Address arithmetic.
append (dynamic) O(1) amortized, O(n) worst Occasional resize copies everything.
insert / delete at index i O(n − i) Shift the tail.
search unsorted O(n) No structure to exploit. Sorted → binary search, O(log n).
slice / copy of k items O(k) A new block plus a copy, in all three languages.

Why append is O(1) amortized: with doubling, the copies over n appends are 1 + 2 + 4 + … + n/2 < n. Add the n writes and it’s under 3n total, so under 3 per append. A constant increment (+4 slots) instead gives n²/8 copies: quadratic. Try both:

Dynamic array: what append really costs
sandbox
filled slots; yellow = copied during the most recent resize; dashed = spare capacity
appends (n)
0
element copies on resize
0
length0
capacity1
work per append0.00
unused slots1
With a multiplicative policy the work per append settles near a constant (≤ 3 for ×2), so append is O(1) amortized. With +4, every few appends copies everything again: total O(n²/8), so work per append keeps climbing. Try ×100 a few times with each.
log (newest first)
Nothing yet. Try an operation.

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Two pointers from both ends. Reverse, palindromic checks, pair sums on sorted data. See two pointers.
  • Array as a hash table. When values are in 1..n, put value v at index v-1 (cyclic sort), or flip a[v-1] negative to mark “seen”. O(1) space, mutates input: say so.
  • Prefix sums / difference arrays. Precompute running totals for O(1) range queries. See prefix sums.
  • 2-D arrays. Rows of arrays, or one flat array with r * cols + c. See matrices.
  • Circular indexing. (i + k) % n turns a fixed array into a ring. See queues.
  • Copy vs view. NumPy slices and C# Span<T> are views (no copy); Python list slices and JS slice are copies.

Pitfalls

Section titled “Pitfalls”
  • Modifying a list while iterating it with for x in a: a.remove(x) skips elements. Use a write pointer or build a new list.
  • Off-by-one on boundaries. Decide inclusive vs exclusive ([lo, hi] vs [lo, hi)) and keep it everywhere.
  • Hidden O(n) calls inside loops: list.pop(0), arr.shift(), list.insert(0, x), x in list, indexOf, slicing. A loop of these is O(n²).
  • Aliasing. b = a copies the reference, not the data. Python [[0] * m] * n creates n references to the same row.
  • Mutating the caller’s input when the spec didn’t allow it. Ask; copy if unsure.
  • Integer overflow in C# (int sums, (lo + hi) / 2). Python ints don’t overflow; JS numbers lose precision past 2^53.

In the interview

Section titled “In the interview”
  • Ask: “Can I modify the input?” and “Do I need to preserve order?” Those two answers pick the technique.
  • State the invariant for each pointer: “Everything before w is kept output; everything between w and r is garbage I can overwrite.”
  • Count your passes and extra space precisely: “one pass, O(1) extra” beats “linear”.
  • Follow-ups: “now do it stably”, “now without extra space”, “what if it doesn’t fit in memory?” (process in chunks, external sort).

Check yourself

Section titled “Check yourself”
Check yourself
pick one
In the Dutch flag partition, after swapping a[mid] with a[hi] (because a[mid] was too big), why don't we advance mid?
Check yourself
pick one
A dynamic array grows by a fixed 1,000 slots each time it's full. What is the total copying cost of n appends?
Check yourself
pick one
In Python, grid = [[0] * 3] * 3; grid[0][0] = 1. What is grid[2][0]?

Practice on your own

Section titled “Practice on your own”

Classic textbook exercises, not gym questions:

  • Remove duplicates from a sorted array in place; then allow each value at most twice.
  • Move all zeros to the end, keeping the order of the other values.
  • Find the one missing number in an array of 0..n (sum, XOR, or cyclic placement).
  • Merge two sorted arrays where the first has enough spare room at the end (fill from the back).

Go deeper

Section titled “Go deeper”
Section titled “Related”
Two pointersPointers from both ends, or fast and slow.
StringsArrays of characters, but usually immutable.
Grids and matricesArrays of arrays and flat 2-D indexing.
Prefix sumsPrecomputed totals over an array.