#in-place
Array Rotation
Array Rotation Array rotation shifts all elements by a fixed offset. Elements that move past one end reappear at the other end. You use it when cyclic structure matters, such as scheduling, buffering, or rearranging data without changing relative order. Problem Given an array $A$ of length $n$ and an integer $k$, rotate the array to the right by $k$ steps. Each element moves from index $i$ to: $$ (i...
Array Compaction
Array Compaction Array compaction removes elements that do not satisfy a predicate by overwriting them with elements that do. It operates in-place and preserves the relative order of retained elements. You use it when filtering data without allocating additional memory. Problem Given an array $A$ of length $n$ and a predicate $P(x)$, remove all elements that do not satisfy $P$, and return the new length. After compaction: for all $i...
Array Partition
Array Partition Array partition rearranges elements so that all elements satisfying a predicate come before those that do not. The operation runs in-place and does not require additional storage. You use it as a primitive in selection, quicksort, filtering, and grouping tasks. Problem Given an array $A$ of length $n$ and a predicate $P(x)$, reorder the array so that: for all indices $i < k$, $P(A[i])$ holds for all indices...
Array Reversal
Array Reversal Array reversal rearranges elements so that the first becomes the last, the second becomes the second last, and so on. You use it as a basic primitive in many algorithms, including rotation, palindrome checks, and two-pointer techniques. Problem Given an array $A$ of length $n$, transform it into: $$ A' = [a_{n-1}, a_{n-2}, \dots, a_0] $$ Algorithm Use two pointers from both ends and swap elements until they...