iv. Classic Array Problems

Short problems with techniques that transfer: maximum subarray, majority and heavy hitters, circular arrays and rotations, and in-place permutation tricks.

Maximum subarray (Kadane)

cur is the best sum of a subarray ending at $i$: extend it or start fresh.

ll best = LLONG_MIN, cur = 0;
for (ll x : a) { cur = max(x, cur + x); best = max(best, cur); }   // non-empty subarray

Proof: Kadane's algorithm is correct

Let $M_i$ be the true maximum sum of a (non-empty) subarray ending exactly at $i$. Claim cur equals $M_i$ after processing $a_i$: any subarray ending at $i$ either is $\{a_i\}$ alone, or extends some subarray ending at $i-1$ by appending $a_i$, so $M_i=\max (a_i,M_{i-1}+a_i)$ — exactly the update cur = max(x, cur + x) with cur holding $M_{i-1}$ by induction (base case $M_0=a_0$, matching cur after the first element since the running sum starts at 0). Since best tracks ${\max }_i{\mathrm{cur}}_i={\max }_i{M}_i$ and every subarray ends at some $i$, best converges to the true maximum over all non-empty subarrays. $■$

The prefix-sum view ${\max }_r(p_r-{\min }_{l<r}{p}_l)$ generalises better:

Variant	Method
empty subarray allowed	start best = 0
length $\ge k$	keep ${\min }_{l\le r-k}{p}_l$
length in $[A,B]$	sliding window minimum of prefixes
sum $\le K$, maximise	set of prefixes, lower_bound(p_r - K)
max product	track both max and min ending here (negatives swap them); zeros reset
circular	$\max (\text{kadane},\text{total}-\text{min-subarray})$; if all are negative, the second term is the empty array, so use plain Kadane
$k$ disjoint subarrays	$O(nk)$ DP with states (used $j$, inside or not); for large $k$ use the Aliens trick, since the answer is concave in $k$
2D max submatrix	fix a pair of rows, collapse columns, Kadane: $O(n^{2}m)$
delete at most one element	DP with states “deletion used / not used”
with point updates, range queries	segment tree node $(\text{sum},\text{best prefix},\text{best suffix},\text{best})$
stock buy-sell, max profit, one transaction	Kadane on consecutive price differences

struct Node { ll sum, pre, suf, best; };
Node merge(Node a, Node b) {
    return {a.sum + b.sum, max(a.pre, a.sum + b.pre), max(b.suf, b.sum + a.suf),
            max({a.best, b.best, a.suf + b.pre})};
}

Proof: the four-value merge is correct

For a range $R=L\cup R^{\prime }$ (left part then right part): sum is additive, trivially correct. pre (best prefix sum of $R$) is either the best prefix of $L$ alone, or all of $L$ plus a prefix of $R^{\prime }$ — and since any prefix of $R^{\prime }$ is at most $R^{\prime }.\mathrm{pre}$, the best such combination is $L.\mathrm{sum}+R^{\prime }.\mathrm{pre}$; taking the max of the two cases is exactly max(a.pre, a.sum + b.pre). Symmetrically suf is max(b.suf, b.sum + a.suf). For best (best subarray sum within $R$): the optimal subarray either lies entirely within $L$ (value $L.\mathrm{best}$), entirely within $R^{\prime }$ (value $R^{\prime }.\mathrm{best}$), or straddles the boundary — in which case it must take a suffix of $L$ and a prefix of $R^{\prime }$ (any other shape is suboptimal: truncating to just the crossing suffix/prefix can only raise or match the sum of a non-maximal partial suffix/prefix), so the straddling case is maximised by $L.\mathrm{suf}+R^{\prime }.\mathrm{pre}$. Taking the max of all three matches the code. $■$

This four-value node is the standard example of a richer segment tree merge, and it shows up again in Segment Tree and in dynamic DP.

Majority and heavy hitters

Boyer-Moore voting: pair each candidate occurrence with a different element and cancel them. A true majority (more than $n/2$) survives every cancellation.

int cand = 0, cnt = 0;
for (int x : a) { if (!cnt) cand = x; cnt += x == cand ? 1 : -1; }
// verify: count(cand) * 2 > n, since a majority may not exist

Proof: Boyer-Moore voting finds the majority if one exists

Think of cnt as a signed tally: each match with cand is $+1$, each mismatch is $-1$. If a true majority element $m$ (occurring $>n/2$ times) exists, claim it survives as the final cand. A prefix where cnt hits exactly 0 pairs off every element it contains into matched $+1/-1$ steps, and each such pairing consumes exactly one occurrence of cand’s then-current value against one occurrence of a different value — so the prefix contains equally many occurrences of whatever value was cand during it as it does of everything else combined, in particular it contains at most half as many occurrences of $m$ as of non-$m$ elements (equality only when every paired-off value was $m$ itself, i.e. the whole prefix alternated $m$ against itself, which is impossible since pairs require a mismatch). So discarding a zero-net prefix removes at most as many copies of $m$ as it removes of non-$m$ elements, meaning $m$‘s excess (count of $m$ minus count of everything else) over the remaining suffix is at least as large as it was over the whole array, hence still positive — $m$ is still a majority of the remaining suffix. Since this holds after every reset, $m$ can never be fully cancelled, so some occurrence of $m$ remains as the uncancelled cand at the end. The verification pass is necessary because if no majority exists, the loop still outputs some candidate. $■$

• More than $n/k$ (Misra-Gries): keep $k-1$ counters; a new value with no free counter decrements all of them. Verify each surviving candidate. $O(nk)$ time, $O(k)$ memory.

Proof: Misra-Gries correctness

Call an element heavy if it occurs more than $n/k$ times. Every decrement step either increments one counter or discards one occurrence each of $k$ distinct values (the current element plus the $k-1$ counted ones, all decremented together) — so each such step removes exactly $k$ occurrences total, at most one of which can belong to any single value. A heavy value occurs $>n/k$ times, so it cannot have every one of its occurrences absorbed into decrement steps (that would require $\ge n/k$ distinct decrement steps $\times 1$ occurrence lost per step just for this value, i.e. more than $n/k$ decrement steps, but there are at most $n/k$ decrement steps total since each removes $k$ of the $n$ occurrences) — so some occurrence of every heavy value survives as an active counter. Since there are only $k-1$ counter slots, there are at most $k-1$ heavy values, consistent with “more than $n/k$ times” being satisfiable by at most $k-1$ disjoint values. Verification is necessary because a surviving candidate’s counted occurrences can undercount its true frequency (some of its occurrences may have been absorbed into decrements), so a candidate might not actually be heavy. $■$

• Sorting: a majority occupies index $\lfloor n/2\rfloor$ after sorting.

Proof: a majority element occupies index $\lfloor n/2\rfloor$ after sorting

After sorting, all occurrences of $m$ (occurring $>n/2$ times) form one contiguous block. Suppose for contradiction the block avoids index $\lfloor n/2\rfloor$; since it’s contiguous, it lies entirely within $[0,\lfloor n/2\rfloor -1]$ or entirely within $[\lfloor n/2\rfloor +1,n-1]$. The first range holds only $\lfloor n/2\rfloor \le n/2$ positions, too few for $>n/2$ occurrences. The second holds $n-\lfloor n/2\rfloor -1=\lceil n/2\rceil -1$ positions, which is $n/2-1<n/2$ when $n$ is even and $(n-1)/2<n/2$ when $n$ is odd — again too few. Both cases contradict $m$ occurring $>n/2$ times, so the block must cover index $\lfloor n/2\rfloor$. $■$

• Bitwise: with a majority guaranteed, take the majority bit in each position.

Method	Time	Space	Note
Boyer-Moore voting	$O(n)$	$O(1)$	optimal; needs verification
hash map counting	$O(n)$	$O(n)$	simplest; also gives all counts
sort, take the middle	$O(n\log n)$	$O(1)$	the majority must occupy index $n/2$
randomised sampling	$O(n)$ expected	$O(1)$	pick a random element, verify; succeeds with probability $>1/2$ per trial
bit-by-bit majority	$O(n\log C)$	$O(1)$	for each bit, take the majority bit
divide and conquer	$O(n\log n)$	$O(\log n)$	the majority of the whole is a majority of some half

• Range majority $a[l..r]$:
  • Randomised: sample about 25 random positions and verify each candidate with binary search over that value’s position list. The failure probability is about $2^{-25}$.
  • Deterministic: (candidate, count) pairs merge like Boyer-Moore, so a segment tree gives a candidate in $O(\log n)$; verify with position lists.
  • Persistent segment tree over values: descend to the half that holds more than $(r-l+1)/2$.
• Streaming relatives: Count-Min sketch (approximate frequencies), HyperLogLog (distinct count), reservoir sampling.

Circular arrays

Technique	When
double the array	windows that may wrap; cyclic shifts as substrings
total minus complement	circular max subarray
rotation starting after the minimum prefix	”a start where every prefix is valid”
fix whether element 0 is used	circular DP: solve twice with element 0 forced in or out
break at a known point	the cycle has an element that is certainly a cut, such as the global maximum

Gas station: with $d_i={\text{gas}}_i-{\text{cost}}_i$, a valid start exists iff $\sum d_i\ge 0$, and it’s the position right after the minimum prefix sum. Equivalently, scan with a tank and restart from $i+1$ whenever the tank goes negative: no station in a failed stretch can be a start.

Proof: the gas station one-pass scan is correct

Necessity of $\sum d_i\ge 0$ is immediate: completing the full circuit requires the tank to return to $\ge 0$, and the tank’s net change over the whole circuit is $\sum d_i$. For sufficiency and the scan: if the tank goes negative while travelling from a tentative start $s$ to station $i$, no station $j\in (s,i]$ can be a valid start. Indeed, starting from $s$, the running tank level on arrival at $j$ was $\ge 0$ (otherwise the scan would already have restarted before $j$), so a run starting at $j$ has no more fuel at every subsequent point than the run from $s$ had — in particular, starting from $s$ the tank was already negative by station $i$, so starting from $j\le i$ it is at least as negative there too, meaning $j$ also fails by station $i$. So restarting at $i+1$ after any failure never skips a valid answer, and since $\sum d_i\ge 0$ guarantees the final restart point (if the scan doesn’t finish from an earlier start) succeeds — the total tank level never dips below the overall minimum prefix sum of $d$, and starting right after that minimum makes every running prefix from there non-negative by definition of “minimum” — one pass suffices. $■$

Cycle lemma (Raney). If integers $x_1..x_n$ sum to $1$, exactly one cyclic shift has all partial sums positive. If each $x_i\le 1$ and the sum is $k>0$, exactly $k$ shifts do. That proves the ballot theorem and $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ (cyclic shifts of a sequence with $n+1$ ups and $n$ downs, made to sum to 1).

Proof: the cycle lemma (case $\sum x_i=1$)

Let $S_0=0,S_1,\dots ,S_n=1$ be the prefix sums, extended periodically by $S_{n+j}:=S_j+1$ (consistent with each $x_i$ repeating every $n$ steps and the total sum being $1$ per period). The shift starting right after index $m$ (i.e. the sequence $x_{m+1},\dots ,x_{m+n}$) has all partial sums positive iff $S_{m+t}>S_m$ for every $t=1,\dots ,n$ — i.e. iff $S_m$ is strictly less than every later term $S_{m+1},\dots ,S_{m+n}$. Let $m^{\text{*}}$ be the last index in $\{0,\dots ,n-1\}$ attaining $\min (S_0,\dots ,S_{n-1})$. Then $S_{m^{\text{*}}}<S_j$ for every $j$ in $(m^{\text{*}},m^{\text{*}}+n)$: for $j$ still inside the first period ($m^{\text{*}}<j<n$), $S_j>S_{m^{\text{*}}}$ because $m^{\text{*}}$ was the last index attaining the minimum, so nothing strictly after it within the period ties or beats it; for $j=n$, $S_n=S_{m^{\text{*}}}+1>S_{m^{\text{*}}}$; for $j$ in the second period ($n<j<m^{\text{*}}+n$, i.e. $j=n+j^{\prime }$ with $0\le j^{\prime }<m^{\text{*}}$), $S_j=S_{j^{\prime }}+1\ge \min (S_0,\dots ,S_{n-1})+1=S_{m^{\text{*}}}+1>S_{m^{\text{*}}}$. So the shift at $m^{\text{*}}$ works. For uniqueness: any other start $m\ne m^{\text{*}}$ has, among $S_{m+1},\dots ,S_{m+n}$, some term equal to $S_{m^{\text{*}}}$ (since $m^{\text{*}}$ or its periodic copy $m^{\text{*}}+n$ falls in that range whenever $m\ne m^{\text{*}}$), and $S_{m^{\text{*}}}=\min (S_0,\dots ,S_{n-1})\le S_m$ — giving a partial sum $S_{m^{\text{*}}}-S_m\le 0$ (or exactly the periodic copy argument when $m^{\text{*}}+n$ is the one in range), so that shift fails to be all-positive. Hence exactly one shift works. The general case ($x_i\le 1$, sum $k$) follows by the same argument applied once per unit of the $k$ “extra” rises: there are exactly $k$ indices tying for the role $m^{\text{*}}$ plays across the $k$ periods needed to accumulate sum $k$, each giving one valid shift. $■$

Minimum refuelling stops: drive until stuck, then retroactively refuel at the biggest station passed (max-heap). The same “take it, regret the worst later” shape appears in regret greedy.

Rotations and in-place rearrangement

• Rotate left by $k$: reverse $[0,k)$, reverse $[k,n)$, reverse all, since $(A^R{B}^R{)}^R=BA$. Normalise $k$ with ((k % n) + n) % n. std::rotate does it directly.

Proof: the triple-reversal rotation identity

Write the array as $AB$ with $A=[0,k)$ and $B=[k,n)$. Reversing a concatenation reverses and swaps its parts: $(XY{)}^R=Y^R{X}^R$ for any sequences $X,Y$ (reversing the whole appends $Y$‘s elements, reversed, before $X$‘s elements, reversed). So $(A^R{B}^R{)}^R=(B^R{)}^R(A^R{)}^R=BA$, which is exactly $AB$ rotated left by $|A|=k$. The three in-place reversals (reverse $A$ to get $A^R$, reverse $B$ to get $B^R$, reverse the whole $A^R{B}^R$) therefore produce $BA$. $■$

• Apply a permutation in place: walk its cycles, or mark visited by negating or adding $n$ to values. The juggling algorithm rotates left by $k$ the same way, in place, by walking $\gcd (n,k)$ cycles directly (no reversal) — same $O(n)$ time, $O(1)$ extra space as the triple-reversal trick, one pass instead of three but with worse cache behaviour, so the reversal method is usually faster in practice despite doing more total work.
• Minimum swaps to sort: $n-$ number of cycles of the permutation mapping positions to sorted positions.

Proof: minimum swaps to sort is $n$ minus the number of cycles

Let $\pi$ be the permutation with $\pi (i)$ = the sorted position of the element currently at $i$ (equivalently, decompose the array into the cycles of “where each element needs to go”). A single swap can merge two cycles into one (swapping two elements in different cycles) or split one cycle into two (swapping two elements in the same cycle) — it changes the cycle count by exactly $\pm 1$, since a swap is a transposition and composing a permutation with a transposition changes its number of cycles by exactly one (standard fact: a transposition $(ab)$ either joins $a$‘s and $b$‘s cycles if they were in different cycles, or splits one cycle into two if $a,b$ were in the same cycle). The sorted array is the identity permutation, which has $n$ cycles (every element a fixed point, a cycle of length 1). Starting from $\pi$ with $c$ cycles, reaching $n$ cycles requires splitting cycles down to all singletons: a cycle of length $\ell$ needs exactly $\ell -1$ swaps to split into $\ell$ singleton cycles (each swap increases the cycle count by at most 1, and $\ell -1$ splits suffice — repeatedly swap an element with the one it should displace), so the total is $\sum ({\ell }_i-1)=n-c$ swaps, and since every swap changes the cycle count by at most 1, no fewer swaps can go from $c$ cycles to $n$ cycles. $■$

• Find the duplicate in $n+1$ values from $[1,n]$ without modifying the array: Floyd’s cycle detection on $i\to a_i$.

Proof: the duplicate is the entry point of the cycle in $i\to a_i$

View $f(i)=a_i$ as a function $\{0,\dots ,n\}\to \{1,\dots ,n\}$ (indices to values). Since the domain has $n+1$ elements mapping into a range of $n$ possible values, $f$ is not injective, so some value is hit by two different indices — meaning the functional graph of $f$ (each $i$ pointing to $f(i)$) has a vertex with in-degree $\ge 2$, which is exactly where two paths merge into a cycle. Floyd’s algorithm finds a point on that cycle, and standard functional-graph argument (see Cycles and Functional Graphs) locates the entry point into the cycle — which is precisely the duplicated value, since that’s the first value reached by two different predecessor chains. $■$

• Missing number(s): XOR of $\mathrm{1..}n$ against the array; for two missing numbers, split by any set bit of their XOR.

Proof: the XOR trick finds missing numbers

XOR-ing $1,\dots ,n$ together with every present array value cancels every value that appears exactly once in the combined multiset (since $x\oplus x=0$), leaving exactly the XOR of the values that appear an odd number of times net — for one missing number, every value $\mathrm{1..}n$ except the missing one appears exactly twice (once in the reference range, once in the array) and cancels, leaving exactly the missing value. For two missing numbers $p,q$: the combined XOR leaves $p\oplus q$. Any set bit $b$ of $p\oplus q$ means $p,q$ differ in bit $b$, so splitting all of $\mathrm{1..}n$ and the array by bit $b$ puts $p,q$ into different groups, each group now missing exactly one number, solvable by the one-missing-number case independently on each half. $■$

• First missing positive in $O(n)$ and $O(1)$ memory: cyclic-sort each value $v\in [1,n]$ into slot $v-1$, then scan.

Proof: cyclic-sort finds the first missing positive in $O(n)$

The invariant maintained is: after processing index $i$, every value $v\in [1,n]$ that has been placed reaches its slot $v-1$ if that slot is reachable (i.e. not already correctly occupied), and values outside $[1,n]$ or duplicates are simply left wherever they land (harmless, since they can never be a missing-positive answer). The swap-into-place loop at each index i only terminates (moves to i+1) when a[i] is already correctly placed, out of range, or a duplicate of the target slot’s value — each of the $O(n)$ possible values is moved into its correct slot at most once over the whole run (a value only moves when landing in the wrong slot, and each move places some value correctly, so there are at most $n$ productive moves total across all $n$ starting positions), giving amortized $O(n)$ total swaps. After this pass, slot $v-1$ holds $v$ for every $v\in [1,n]$ that was present in the original array; the final scan finds the first slot $i$ with $a_i\ne i+1$, which is exactly the smallest positive integer not present. $■$

• Next permutation: find the last $i$ with $a_i<a_{i+1}$, swap $a_i$ with the last element greater than it, reverse the suffix. The $k$-th permutation comes from the factorial number system.

Proof: the next-permutation algorithm is correct

The suffix starting at $i+1$ is, by the choice of $i$ (the last ascent), weakly decreasing — every permutation of that suffix’s multiset that is lexicographically larger than the current one must therefore change a prefix of the suffix, and the smallest change that increases the value is at position $i$ itself: replacing $a_i$ with the smallest element in the suffix that is still $>a_i$ (which, since the suffix is decreasing, is found by scanning from the end for the last element greater than $a_i$) gives the smallest possible increase at that position. Once $a_i$ is fixed to this new value, the remaining suffix (the old $a_i$ now inserted into the decreasing tail, still decreasing after the swap since we swapped in the smallest valid element from a decreasing sequence) must be arranged in the smallest possible order, which is strictly increasing — exactly what reversing the (still-decreasing) suffix produces. $■$

More in-place patterns:

Task	Technique
remove duplicates from a sorted array	two pointers: unique(all(a))
partition by a predicate	Dutch national flag
move zeros to the end	a write pointer trailing a read pointer
reverse in groups of $k$	repeated reverse on subranges

Matrix transformations

Rotations are compositions of transpose $(i,j)\to (j,i)$ and reversals:

Operation	Recipe	Map for an $n\times n$ matrix
rotate 90° clockwise	transpose, then reverse each row	$(i,j)\to (j,n-1-i)$
rotate 90° counter-clockwise	transpose, then reverse row order	$(i,j)\to (n-1-j,i)$
rotate 180°	reverse row order and each row	$(i,j)\to (n-1-i,n-1-j)$
flip top-bottom / left-right	reverse row order / each row
main-diagonal mirror	transpose	$(i,j)\to (j,i)$
anti-diagonal mirror	reverse rows, transpose, reverse rows

In the transpose loop start j at i + 1, otherwise every pair is swapped twice. For an $r\times c$ matrix, allocate a $c\times r$ result: res[j][r-1-i] = m[i][j].

Derive, don't memorise

Rotate the corner $(0,0)$ in your head and see where it lands. Transpose sends $(i,j)\to (j,i)$; reversing rows sends $(i,j)\to (i,n-1-j)$. Composing gives $(i,j)\to (j,n-1-i)$, which is exactly clockwise rotation. Two seconds of checking beats a memorised table you might have backwards.

Proof: the transpose-then-reverse recipes rotate correctly

Transpose sends $(i,j)\to (j,i)$. Applying “reverse each row” afterward acts on the transposed matrix’s own row/column indices $(r,c)\to (r,n-1-c)$; substituting the transposed position $(r,c)=(j,i)$ gives $(j,n-1-i)$. So the composition sends $(i,j)\to (j,i)\to (j,n-1-i)$, matching the table’s clockwise formula exactly. Sanity check against the corners: the top-left $(0,0)\to (0,n-1)$ (top-right) and the top-right $(0,n-1)\to (n-1,n-1)$ (bottom-right) — consistent with a clockwise quarter turn, where the top edge swings down to become the right edge. The other three recipes (counter-clockwise: transpose then reverse row order; 180°: reverse rows and reverse each row; flips: a single reversal) compose the same two primitives ($(i,j)\to (j,i)$ for transpose, $(i,j)\to (n-1-i,j)$ for reversing row order, $(i,j)\to (i,n-1-j)$ for reversing each row) and are checked the same way. $■$

Diagonals: anti-diagonals are indexed by $i+j$ and main diagonals by $i-j$ (offset by $c-1$). Grid DPs that move right/down process anti-diagonals in order.

Spiral order needs the two guards before the bottom row and left column passes, or a single remaining row or column is printed twice.