Data Structures & Algorithms · Section 3
The foundational array patterns — prefix and suffix sums, difference arrays, Kadane's algorithm, cyclic sort, the Dutch national flag partition, matrix traversal, and the reversal trick for rotation — plus the Python tools (comprehensions, accumulate, zip, enumerate, slicing) built to support them, and the aliasing pitfall every one of them can fall into.
What is true here
What you will be able to do
The core array patterns, from how memory layout gives O(1) access to the classic named algorithms built on top of it.
An array stores its elements back-to-back in memory, so the address of element i can be computed directly (base address + i * element size) — no searching required. That direct computation is why items[i] is O(1).
Remember: Index access is O(1) because the elements sit next to each other in memory, letting the address be computed directly instead of searched for.
See also: list fast ops
A classic array has a fixed capacity, set at creation. Python's list is dynamic — it over-allocates spare capacity behind the scenes and reallocates to a bigger block automatically when it runs out, which is what makes .append() O(1) amortized (§2).
Think of it as
Thinking of Python's `list` as 'the array from other languages' is close enough for most problems, but the sizing model differs: a fixed array either has room or it does not (and resizing is the programmer's job), while `list` grows on its own behind `.append()`, trading a little extra memory for never needing to manage capacity by hand.
Remember: Python's list is a dynamic array — it manages its own growing capacity, unlike a fixed-size array where the programmer must plan for it.
The same array can be walked forward (start to end), backward (end to start), or with a step (every k-th element) — the direction and stride you pick shape what an algorithm can do in one pass.
What we're doing: Confirm forward, backward, and skip traversal each produce the expected order.
[50, 40, 30, 20, 10] [10, 30, 50]Why this works: The slice step controls both direction (negative reverses) and stride (skips elements) — one notation covers all three traversal patterns.
Remember: items[::-1] traverses backward; items[::k] skips — the slice step controls both direction and stride.
An in-place algorithm rewrites the input using O(1) extra space; building a new list uses O(n) extra space but is often simpler to write and reason about. Both can be correct — the choice is a real space/simplicity trade-off, not just style.
Think of it as
In-place reversal swaps elements within the same list, using two index variables and no extra container — O(1) space. items[::-1] is simpler to read but allocates a full second list — O(n) space. Neither is universally 'better'; a huge list under memory pressure favors in-place, a small list favors whichever reads clearer.
What we're doing: Reverse the same list both in place and by building a new one, and confirm they produce the same order.
[4, 3, 2, 1] [4, 3, 2, 1] [4, 3, 2, 1]Why this works: reverse_in_place both returns [4, 3, 2, 1] AND leaves the original a mutated to [4, 3, 2, 1] — proof it changed the same object rather than building a new one, unlike reverse_new, whose input a fresh [1, 2, 3, 4] is untouched.
The problem explicitly requires the in-place, O(1)-space version taught above — s[::-1] is disallowed by the constraints.
A follow-up asks for the O(1)-space, in-place solution specifically — compare it against the simpler build-a-new-list version first.
Remember: In-place trades simplicity for O(1) space; building a new list trades O(n) space for simplicity — pick deliberately, and make a mutating function's effect on its input obvious.
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.
Think of it as
prefix[k] holds the total of everything before index k. The sum of a range [i, j] is prefix[j+1] - prefix[i] — everything up to j, minus everything before i, leaving exactly the range in between. Paying O(n) once to build the array turns every future range-sum query into O(1) instead of O(range length).
What we're doing: Build a prefix-sum array once, then answer a range-sum query in O(1).
[0, 2, 6, 7, 13, 16] 11Why this works: prefix[4] (13) is everything through index 3; prefix[1] (2) is everything before index 1 — subtracting leaves exactly indices 1 through 3, whose real sum (4 + 1 + 6) is 11, confirmed by both the direct calculation and the O(1) formula agreeing.
Forgetting the +1 shift between a prefix array and the original indices
Wrong
Better
What you see: range_sum_buggy(prefix, 1, 3) on [2, 4, 1, 6, 3] returns 5, not 11 — it silently excludes the element at index 3 from the sum.
Why: prefix[k] represents the sum of the first k elements (indices 0..k-1), not "up to index k" — so including index j in an inclusive range requires prefix[j + 1], not prefix[j]. Skipping the +1 shift is the single most common prefix-sum bug, and it never crashes — it just silently returns a slightly-too-small sum.
This IS the prefix-sum array itself — the expected output at each index is exactly prefix[i+1] from this concept.
The same prefix idea, with multiplication instead of addition: a running prefix product from the left, a running suffix product from the right, combined at each index.
Remember: 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].
See also: suffix sums · difference arrays
A suffix-sum array mirrors a prefix sum, but built from the end: suffix[k] holds the total of everything from index k to the end. Useful whenever a problem needs "everything after this point" instead of "everything before it".
Think of it as
Building right to left instead of left to right is the entire difference from a prefix sum — suffix[k] = suffix[k+1] + nums[k], the mirror image of prefix[k+1] = prefix[k] + nums[k-1]. Some problems (comparing "everything to my left" against "everything to my right") need both arrays at once.
What we're doing: Build a suffix-sum array and confirm suffix[0] equals the total of the whole array.
[16, 14, 10, 9, 3, 0]Why this works: suffix[0] is 16 — the sum of the entire array (2+4+1+6+3=16) — exactly as expected, since "everything from index 0 to the end" is the whole array.
Build the mirror-image running total from the left first — then try adapting your solution to run from the right instead, which is exactly a suffix sum.
Needs both directions at once: a prefix product from the left and a suffix product from the right, combined at each index.
Remember: A suffix sum is a prefix sum built from the other end — reach for it whenever a problem needs "everything after this point" rather than "everything before it".
See also: prefix sums
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).
Think of it as
This is prefix sums used in reverse. Instead of building a running total from real values, you record WHERE a change starts and stops, and let a single final prefix-sum pass turn those markers into the real values — the mirror image of using prefix sums to answer range queries fast.
What we're doing: Apply two overlapping range updates in O(1) each, then recover the real values with one prefix-sum pass.
[0, 5, 7, 7, 2, 0]Why this works: Index 1-3 get +5 from the first update; indices 2-4 get an additional +2 from the second — index 2 and 3 (inside both ranges) correctly show 7 (5+2), index 1 shows 5 (only the first range), and index 4 shows 2 (only the second) — exactly matching two overlapping range-add operations applied directly.
The final step of the difference-array trick, on its own — a plain prefix-sum pass. Good warm-up before combining it with range markers.
This is the exact technique taught above — mark +val at each range's start and -val just after its end, then take one final prefix sum.
Remember: 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).
See also: prefix sums
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.
Think of it as
At every position, ask one question: is the running sum so far HELPING or HURTING? If current + x is worse than starting fresh at x alone, the running sum has gone negative enough that carrying it forward only drags the total down — so drop it and start over from x. Track the best total seen at any point, since the best subarray does not have to end at the last element.
What we're doing: Find the maximum-sum contiguous subarray of a list with both positive and negative numbers.
6Why this works: The subarray [4, -1, 2, 1] sums to 6, the largest of any contiguous run in this list — Kadane's finds it in one O(n) pass by always keeping either the best run ending at the current position, or restarting when that run has gone net-negative.
Initializing the running sum to 0 instead of the first element
Wrong
Better
What you see: On an all-negative array [-5, -2, -8, -1], max_subarray_buggy returns 0 — but 0 is not the sum of any subarray of this list; the correct answer is -1 (the single-element subarray [-1]).
Why: Starting best at 0 silently treats 'the empty subarray' as a valid candidate, which is only correct if the problem allows an empty subarray (most maximum-subarray problems do not). Starting both trackers at nums[0] instead guarantees the first candidate is a REAL subarray — a single element — so an all-negative array correctly returns its least-negative element rather than a phantom 0.
Track the lowest price seen so far and the best profit so far in one pass — the same "running value, updated once per element" shape as current/best here.
This is Kadane's algorithm exactly as taught above — implement current = max(x, current + x) and track best separately.
Remember: 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.
See also: prefix sums
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.
Think of it as
Instead of comparing elements to each other like a normal sort, cyclic sort asks one question per element: 'is this value already at its home index?' If not, swap it directly to where it belongs, and check that position's new value too — do not move on until the CURRENT index holds its correct value. This only works because the value range (1..n) exactly matches the index range, so every value has exactly one valid home.
What we're doing: Sort an array of the numbers 1 through 5 (in some order) in place, without any comparisons between elements.
[1, 2, 3, 4, 5]Why this works: Every value ends up at index (value - 1) with zero comparisons between different values — only equality checks against each position's own correct value — which is why this beats a general O(n log n) sort for this specific, narrow case.
Advancing i unconditionally, even right after a swap
Wrong
Better
What you see: cyclic_sort_buggy([2, 3, 4, 1]) returns [3, 2, 1, 4] — not sorted — while the fixed version correctly returns [1, 2, 3, 4] on the same input.
Why: A swap can bring in a value that is ALSO not home yet — on a long enough cycle of misplaced values, one swap is not enough to fix a position. Advancing i unconditionally abandons that position after only one attempt, and if the position it swapped a wrong value INTO was already behind i, it is never revisited — the array is left partially, silently unsorted.
Cyclic-sort the array toward its home positions (or track which index never got its correct value) to spot the one number that never showed up.
The direct generalization of Missing Number to multiple gaps: after cyclic-sorting, every index whose value is not index+1 names a missing number.
Remember: 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.
See also: dutch national flag
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.
Think of it as
Three regions grow from both ends toward the middle as mid scans through: everything before low is confirmed 0s, everything from low to mid-1 is confirmed 1s, everything after high is confirmed 2s, and mid is the current unknown boundary. A 0 gets swapped down to low (both pointers advance, since the swapped-in value at mid is now known to be 1 or already scanned); a 1 just advances mid; a 2 gets swapped up to high — but mid must NOT advance yet, because the value swapped in from high has never been examined.
What we're doing: Sort an array of 0s, 1s, and 2s in one pass using the three-pointer partition.
[0, 0, 1, 1, 2, 2]Why this works: All six elements land in three correctly ordered blocks — 0s, then 1s, then 2s — using only swaps and pointer moves, no general comparison sort, confirming the three-region invariant held throughout the single pass.
Advancing mid after swapping with high
Wrong
Better
What you see: sort_colors_buggy([1, 2, 0]) returns [1, 0, 2] — not sorted — while sort_colors_fixed correctly returns [0, 1, 2] on the same input.
Why: Swapping with high brings an UNEXAMINED value into position mid — it could be a 0, a 1, or another 2. Advancing mid immediately skips examining it, so a 0 that landed there by chance never gets moved to the low region. Only a swap with low is safe to pair with advancing mid, because the value coming from low in this algorithm's invariant is always already known to be a 1 or unexamined-but-already-passed.
The two-region version of this same partition idea — one write pointer instead of two, since there is no "high" group to also track.
This is the Dutch national flag problem exactly as taught above — implement the low/mid/high three-pointer partition in one pass.
Remember: 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.
See also: cyclic sort
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.
Think of it as
A spiral traversal is four shrinking rectangles peeled off in turn: top row left-to-right, right column top-to-bottom, bottom row right-to-left, left column bottom-to-top — then the boundary shrinks inward by one on all four sides and repeats. Tracking four boundaries (top, bottom, left, right) instead of a single row/column index is what makes the shrinking rectangle manageable.
What we're doing: Traverse a 3x3 matrix in spiral order, from the outside ring inward.
[1, 2, 3, 6, 9, 8, 7, 4, 5]Why this works: The order (top row, right column, bottom row, left column, then the single remaining center cell) matches exactly what tracing four shrinking boundaries around a 3x3 grid by hand produces — every cell visited exactly once.
A warm-up in matrix indexing: swap matrix[i][j] with matrix[j][i] to flip the matrix over its main diagonal.
This is the spiral traversal taught above — track four shrinking boundaries (top, bottom, left, right) and peel off one side at a time.
Remember: 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.
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.
Think of it as
Reversing the whole array puts every element in reverse order, including the two halves that need to swap places — but each half is now ALSO internally backwards. Reversing each half back undoes just that internal backwardness, leaving the two halves correctly swapped and each individually back in original order.
What we're doing: Rotate an array right by 3 using three reversals, with no extra array.
[5, 6, 7, 1, 2, 3, 4]Why this works: The last 3 elements (5, 6, 7) moved to the front, and the rest kept their relative order — exactly a rotate-right-by-3 — achieved with three in-place reversals and no second array.
The exact two-pointer reversal mechanic this rotation trick is built from — swap ends inward until the pointers meet.
This is the reversal trick taught above — reverse the whole array, then reverse the first k, then reverse the rest.
Remember: 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.
See also: in place vs building new
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.
Think of it as
Filling from the front seems natural, but it overwrites nums1's own not-yet-compared values before they are used. Filling from the back instead writes into the trailing empty slots first — space that starts out unused — so every write lands somewhere nothing important still needs, working backward until every element has been placed exactly once.
What we're doing: Merge nums2 into nums1 in place, using the trailing zeros in nums1 as the only extra space.
[1, 2, 3, 4, 5, 6]Why this works: Every one of the six values ends up in sorted order, using only the trailing space nums1 already had — no second array was ever allocated, because filling from the back means every write lands on space that either started empty or already had its value copied out.
Merging from the front, directly into nums1
Wrong
Better
What you see: merge_from_front_buggy([1, 3, 5, 0, 0, 0], 3, [2, 4, 6], 3) returns [1, 2, 4, 0, 0, 0] — the original 3 and 5 are gone, overwritten before they were ever compared, and 6 never made it into the result at all.
Why: Writing nums2[j]'s value directly into nums1[i] destroys nums1's own value at that position before the algorithm has had a chance to compare it against anything — there is no spare space at the FRONT to absorb an overwrite. The back-filling version works precisely because the trailing zeros give it space nothing is depending on yet.
This is the exact problem taught above — merge nums2 into nums1's own trailing space, filling from the back.
A different shape of "merge" — sort by start time first, then sweep once, extending the last interval whenever the next one overlaps it.
Remember: 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.
See also: in place vs building new
The standard-library and syntax tools that make array patterns concise in Python specifically.
[expr for x in items if condition] both transforms (expr) and filters (if condition) in one line — faster to write and usually faster to run than an equivalent manual loop with .append().
What we're doing: Filter a list of prices down to only those above a threshold, in one line.
[25, 42]Why this works: The comprehension reads as "the value p, for each p in prices, only where p > 10" — the same logic a manual loop with an if and an append would need three lines to express.
Remember: A list comprehension folds a transform and a filter into one line — reach for it before writing a manual loop with .append().
itertools.accumulate(nums) builds the running-total array directly — the same values a hand-written prefix-sum loop produces, without the leading 0 that a manually built prefix array usually has.
What we're doing: Build a running-total array with accumulate() and compare it to a hand-written prefix sum.
[2, 6, 7, 13, 16]Why this works: Each value is the running total up to that point (2, then 2+4=6, then 6+1=7, ...) — exactly the values a manual prefix-sum loop computes, built in one call instead of a hand-written loop.
list(accumulate(nums)) solves this in one line — compare it against a hand-written loop.
accumulate() takes an optional function argument — accumulate(nums, operator.mul) gives a running PRODUCT instead of a sum, directly useful here.
Remember: itertools.accumulate(nums) is the running-total array, built for you — reach for it before hand-writing a prefix-sum loop.
See also: prefix sums
zip(a, b) walks two (or more) sequences together, pairing up elements at the same position — no manual index bookkeeping needed. It stops at the shortest input.
What we're doing: Pair up two parallel lists by position without a manual index.
[('Ada', 90), ('Grace', 95)]Why this works: Each tuple pairs the two lists' elements at the same position, in order — the entire point of zip when two sequences need to be walked together.
for a, b in zip(s, t) walks both strings together in one line — build the character mapping as you go.
After sorting both strings, all(a == b for a, b in zip(sorted(s), sorted(t))) checks them position by position without a manual index.
Remember: zip(a, b) pairs elements by position without a manual index — it silently stops at the SHORTEST input if the lengths differ.
enumerate(items) yields (index, value) pairs while looping — no need for a separate counter variable manually incremented each time.
What we're doing: Loop with both a 1-based position and the value, without a manual counter.
1 x
2 y
3 zWhy this works: Each pair (i, v) is exactly the position and value at that step — the same thing a manually incremented counter variable would track, without the separate counter.
for i, num in enumerate(nums) gives both the index to return and the value to check against the hash map, in one line.
A variant that needs the POSITION of a duplicate (not just whether one exists) reaches for enumerate() instead of a plain for-in loop.
Remember: enumerate(items) replaces a manually incremented counter — add start=N to shift where the count begins.
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.
Think of it as
Negative indices are just position minus length — a[-1] is shorthand for a[len(a) - 1] — so they work anywhere a positive index does, including inside a slice. A slice's stop index is always excluded (half-open), which is why a[i:j] has exactly j - i elements, not j - i + 1.
What we're doing: Confirm negative indexing, slicing bounds, and reversal all behave as expected on the same list.
5 [5, 4, 3, 2, 1] [2, 3, 4]Why this works: a[-1] correctly resolves to the last element without needing len(a); a[1:4] holds exactly 4-1=3 elements ([2, 3, 4]), confirming the half-open, exclusive-stop rule.
s[::-1] solves this in one line — though the problem's in-place constraint means you need the two-pointer version instead, see In-Place vs Building New.
nums[:] = nums[-k:] + nums[:-k] rotates in one line using exactly the negative-index slicing taught here.
Remember: 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.
See also: traversal patterns
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.
Think of it as
A name in Python is a label, not a box — b = a puts a second label on the exact same object, it never duplicates it. Any mutation through either label (append, item assignment, sort) is visible through both, because there was only ever one list. .copy() (or a[:]) is what actually builds a second, independent object.
What we're doing: Compare mutating through an alias versus mutating through a real copy.
[1, 2, 3, 4] [1, 2, 3, 4] [1, 2, 3, 99]Why this works: original and alias both show [1, 2, 3, 4] because they are two names for the same object — appending through EITHER name mutates the one list both point at. copy shows [1, 2, 3, 99] because it is a separate object entirely, unaffected by alias's append and only changed by its own.
Assuming .copy() protects nested mutable objects too
Wrong
Better
What you see: After shallow[0][0] = 1, the ORIGINAL grid also shows [[1, 0], [0, 0]] — even though grid and shallow are genuinely different list objects.
Why: .copy() only copies the OUTER list — each inner list is still the same shared object referenced by both grid and shallow, exactly like a plain assignment would share it. A shallow copy protects against changes made by APPENDING or REMOVING items from the outer list, but not against mutating an object one of those items itself refers to — that needs copy.deepcopy() instead.
Mutating the grid in place is intended here — but be deliberate about it: pass the SAME grid down each recursive call on purpose, not an accidental alias of only part of it.
The exact deep-copy problem this concept warns about, at graph scale: a shallow copy of a node still shares its neighbor list with the original, so a visited-to-clone map is needed to build a genuinely independent structure.
Remember: 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().
See also: in place vs building new