beginnerintermediateadvanced

Algorithms · Arrays and Lists

Arrays and Lists

The classic array patterns — prefix sums, Kadane's, cyclic sort, 3-way partition — and the Python tools behind them

Prefix sumsO(n) build, O(1) range query
Kadane'smax subarray in one pass
In place vs newO(1) space vs simplicity
Aliasingb = a shares one list, not two

1.Prefix sums

A prefix-sum array stores the running total up to each index, built once in O(n). After that, the sum of any range [i, j] is one subtraction, O(1), instead of re-adding that range every time.

Key features

prefix has length n + 1: prefix[0] = 0, and prefix[k] = sum of the first k elements
Range sum [i, j] (inclusive) is prefix[j + 1] - prefix[i]
Building the prefix array is O(n); each range query afterward is O(1)
itertools.accumulate builds the same running-total array, without the leading 0 — see this section's Python-tools group

One O(n) build, then O(1) per range query

build prefix[]

O(n), once

prefix[j+1] - prefix[i]

O(1), any range

prefix[k] is the sum of the first k elements — an inclusive range [i, j] is prefix[j + 1] - prefix[i], never prefix[j] - prefix[i].

2.Kadane's algorithm (maximum subarray)

Kadane's algorithm finds the largest sum of any contiguous subarray in one O(n) pass, by deciding at each element: extend the current run, or start a new one from here — whichever gives a bigger sum.

Key features

current tracks the best sum of a subarray ENDING at the current position
best tracks the best sum seen anywhere so far — it does not have to end at the current position
current = max(x, current + x) is the whole trick: carry the running sum forward only if it still helps
Must start current and best at nums[0], not 0 — an all-negative array has no valid answer of 0

Watch Kadane's scan the array, one decision at a time

-2

-3

-1

-5

0.0s/ 17.8s

9 numbers, positive and negative. Find the contiguous stretch whose numbers add up to the largest total.

At each element, current = max(x, current + x) — keep extending the run only while it still helps, and always track best separately since the best run does not have to end at the last element.

3.Cyclic sort pattern (numbers in range 1..n)

When an array holds numbers from 1 to n (one per index, no gaps), each value already knows exactly where it belongs — value v belongs at index v - 1. Repeatedly swapping each element into its home position sorts the whole array in O(n), without comparisons.

Key features

Only applies when values are drawn from 1..n (or 0..n-1), one slot per value
Value v belongs at index v - 1 (or index v, for a 0..n-1 range)
Runs in O(n) — each element is moved to its final position at most once overall
The classic follow-up: any index NOT holding its correct value after a cyclic sort reveals a missing or duplicate number

Swap each value to its own home index

value v

belongs at index v-1

swap

into place

recheck

don't advance until correct

Cyclic sort only applies to values drawn from 1..n — swap each value to its home index (v - 1), and do not advance past a position until it holds its own correct value.

4.Dutch national flag / 3-way partition

Given an array of only three distinct values (classically 0, 1, 2), the Dutch national flag algorithm sorts it in one O(n) pass using three pointers — low, mid, high — with no full comparison sort needed.

Key features

low marks the boundary of confirmed 0s; high marks the boundary of confirmed 2s; mid is the current scan position
On a 0: swap with low, advance BOTH low and mid
On a 1: it is already in the right region — advance mid only
On a 2: swap with high, advance high only — mid must stay, since the newly-swapped-in value is still unexamined

Watch low, mid and high partition the array live

low

mid

high

low, mid, high = 0, 0, n-1

0.0s/ 13.1s

6 values, each 0, 1, or 2. Group them in one pass: all the 0s first, then the 1s, then the 2s.

A swap with high must NOT advance mid — the value just swapped in has never been examined — but a swap with low can, since only two of the three swap directions bring in an unknown value.

5.Merging two sorted arrays in place

When the first array has enough trailing empty space to hold both, two sorted arrays can be merged into it without extra memory — by filling from the BACK, largest values first, so nothing gets overwritten before it is read.

Key features

Requires nums1 to already have enough trailing space (length m + n) to hold the merged result
Three pointers: i at the end of nums1's real data, j at the end of nums2, k at the very end of the combined space
Fill from the back: place the larger of nums1[i]/nums2[j] at position k, then move that pointer and k backward
Filling from the front instead overwrites nums1 values still needed for comparison — the entire reason this trick works backward

Fill backward, largest first

nums1 tail

i, real data

nums2 tail

j, real data

larger -> k

write from the back

When merging into an array with trailing space, fill from the BACK, largest values first — filling from the front overwrites values that still need to be read.

6.list.copy() vs assignment (aliasing pitfall)

b = a does not copy the list — it gives a second name to the SAME list object, so changing b also changes a. b = a.copy() makes a genuinely separate list.

Key features

b = a: b and a are two names for the SAME list object — mutating one affects the other
b = a.copy() (or a[:]): b is a genuinely separate list object with the same elements
A copy is SHALLOW — if a holds other mutable objects (like nested lists), those inner objects are still shared between a and its copy

One object, two names — until you copy

a = [1, 2, 3]

one list object

b = a

same object, new label

b = a.copy()

a real second object

b = a shares one list under two names; b = a.copy() makes a real second list — but even that copy is shallow, so nested mutable objects (like a list of lists) are still shared unless you use copy.deepcopy().

7.Difference arrays (range-update trick)

To add a value across a whole range [start, end] many times, mark just two positions per update (+val at start, -val at end+1), then take a prefix sum once at the end. Each update becomes O(1) instead of O(range length).

Key features

diff[start] += val marks a change starting there; diff[end + 1] -= val cancels it right after the range ends
Each range update costs O(1) — two array writes, regardless of how large the range is
One final prefix-sum pass over diff, O(n), turns the markers into the real per-index values

To add a value across a range many times, mark the start and the position just after the end, and take one prefix sum at the very end — each update becomes O(1) instead of O(range length).

8.Matrix traversal (row-major, column-major, diagonal, spiral)

A 2D grid can be walked row by row (row-major), column by column (column-major), diagonally, or in a shrinking spiral — each visits every cell exactly once, in a different order a problem might specifically ask for.

Key features

Row-major: outer loop over rows, inner loop over columns (Python's natural nested-list order)
Column-major: outer loop over columns, inner loop over rows — the transpose of row-major
Spiral: four boundaries (top, bottom, left, right) that shrink inward by one after each full lap
A grid is a graph in disguise — the same 4-directional movement reappears in graph traversal (§18)

Spiral traversal is four shrinking boundaries (top, bottom, left, right), peeled off one side at a time — not a single row/column index trying to do all four jobs at once.

9.Rotating an array (reversal trick)

To rotate an array right by k in place: reverse the whole array, then reverse the first k elements, then reverse the rest. Three O(n) reversals, O(1) extra space, no separate rotated copy needed.

Key features

Reverse the whole array first, then reverse each of the two resulting pieces separately
The split point after the first reversal is index k (k = rotation amount, wrapped by len(nums) if k > n)
Three passes, each O(n), for O(n) total time and O(1) extra space — no second array allocated

Rotate right by k: reverse everything, then reverse the first k, then reverse the rest — three O(n) reversals beat building a rotated copy when O(1) extra space matters.

10.Negative indexing and slicing (`a[::-1]`, `a[i:j]`)

A negative index counts from the end: a[-1] is the last element, a[-2] the second-to-last. A slice a[i:j] takes elements from i up to (not including) j, and a[::-1] reverses the whole sequence.

Key features

a[-1] is the last element; a[-n] is the n-th from the end
a[i:j] is half-open: it includes index i, excludes index j, and has exactly j - i elements
a[::-1] reverses via a step of -1 — it returns a new list, it does not reverse in place
a[:i] + a[i:] always reconstructs the original sequence, for any valid i

A slice's stop index is always EXCLUDED — a[i:j] has j - i elements, never j - i + 1 — and a[::-1] is a new, reversed list, not an in-place reversal.

Spotted a mistake on this page? Tell us.

Read Sheet