Common Array Patterns - Learning Module

Loading content...

0/276

In-Place Transformations

Mastering Space-Efficient Array Manipulation

In-place transformations modify an array using only O(1) auxiliary space—no extra arrays proportional to input size. This constraint appears constantly in real-world systems:

Memory-constrained environments: Embedded systems, mobile devices
Performance optimization: Avoiding allocation/deallocation overhead
Interview expectations: Often an explicit constraint or follow-up question
Streaming data: Processing elements as they arrive without buffering

These techniques require careful thinking about element placement, invariant maintenance, and pointer management. They represent a higher level of algorithmic craftsmanship—solving problems with minimal resources.

What You Will Master

By the end of this page, you will deeply understand array partitioning, the Dutch National Flag algorithm for three-way partition, removing duplicates in-place, shuffling algorithms (Fisher-Yates), and general techniques for O(1) space manipulation.

Array Partitioning: The Foundation

Partitioning rearranges an array so that elements satisfying a condition come before elements that don't. It's the core operation of quicksort and appears in many selection and rearrangement problems.

Problem: Given an array and a pivot value, rearrange so all elements ≤ pivot come before all elements > pivot.

This is equivalent to separating elements into two groups while preserving the array's size.

partition.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Partition array around a pivot value.
 * All elements ≤ pivot are moved to the front.
 * 
 * Uses the "Lomuto partition scheme":
 * - Maintain boundary 'i' for elements ≤ pivot
 * - Scan with 'j', swap when element ≤ pivot found
 * 
 * Time:  O(n) — single pass
 * Space: O(1) — in-place swaps only
 * 
 * @returns Final position of the partition boundary
 */
function partition(arr: number[], pivot: number): number {
    let i = 0; // Boundary: arr[0..i-1] contains elements ≤ pivot
    
    for (let j = 0; j < arr.length; j++) {
        if (arr[j] <= pivot) {
            // Swap arr[j] into the "≤ pivot" region
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
        }
    }
    
    return i; // Number of elements ≤ pivot
}
 
// Example
const arr = [3, 8, 2, 5, 1, 4, 7, 6];
const boundary = partition(arr, 4);
console.log(arr);       // [3, 2, 1, 4, 8, 5, 7, 6] (order varies)
console.log(boundary);  // 4 (first 4 elements are ≤ 4)

Visualization:

Initial:  [3, 8, 2, 5, 1, 4, 7, 6]  pivot=4
           i,j

j=0: 3 ≤ 4 → swap(0,0), i=1
j=1: 8 > 4 → skip
j=2: 2 ≤ 4 → swap(1,2), i=2  → [3, 2, 8, 5, 1, 4, 7, 6]
j=3: 5 > 4 → skip
j=4: 1 ≤ 4 → swap(2,4), i=3  → [3, 2, 1, 5, 8, 4, 7, 6]
j=5: 4 ≤ 4 → swap(3,5), i=4  → [3, 2, 1, 4, 8, 5, 7, 6]
j=6: 7 > 4 → skip
j=7: 6 > 4 → skip

Result: [3, 2, 1, 4 | 8, 5, 7, 6]
         ≤ pivot    > pivot

Invariant Thinking

The key to partition algorithms is maintaining an invariant: 'arr[0..i-1] contains only elements satisfying the condition.' After each iteration, this remains true. When the loop ends, the invariant guarantees correctness.

Quicksort's Partition: Placing the Pivot

Quicksort's partition scheme differs slightly—it places the pivot element in its final sorted position, with all smaller elements before it and all larger after.

The Lomuto Scheme (Simple):

Choose the last element as pivot. Partition around it, then swap pivot into its final position.

lomutoPartition.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Lomuto partition scheme for quicksort.
 * Uses last element as pivot.
 * 
 * After partition:
 * - arr[lo..pivotIdx-1] < pivot
 * - arr[pivotIdx] = pivot (in final position)
 * - arr[pivotIdx+1..hi] ≥ pivot
 * 
 * @returns Index where pivot ends up
 */
function lomutoPartition(
    arr: number[],
    lo: number,
    hi: number
): number {
    const pivot = arr[hi];  // Choose last element as pivot
    let i = lo;             // Boundary for elements < pivot
    
    for (let j = lo; j < hi; j++) {
        if (arr[j] < pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
        }
    }
    
    // Place pivot in its final position
    [arr[i], arr[hi]] = [arr[hi], arr[i]];
    
    return i;
}
 
// Quicksort using Lomuto partition
function quicksortLomuto(
    arr: number[],
    lo: number = 0,
    hi: number = arr.length - 1
): void {
    if (lo < hi) {
        const pivotIdx = lomutoPartition(arr, lo, hi);
        quicksortLomuto(arr, lo, pivotIdx - 1);
        quicksortLomuto(arr, pivotIdx + 1, hi);
    }
}

The Hoare Scheme (Efficient):

Uses two pointers from opposite ends, converging toward the middle. More efficient (fewer swaps on average) but slightly more complex.

hoarePartition.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Hoare partition scheme.
 * Uses two pointers converging from opposite ends.
 * 
 * Typically ~3x fewer swaps than Lomuto on average.
 * 
 * Note: Pivot doesn't necessarily end up at returned index.
 * The returned index is where the partition splits.
 */
function hoarePartition(
    arr: number[],
    lo: number,
    hi: number
): number {
    const pivot = arr[Math.floor((lo + hi) / 2)];
    let i = lo - 1;
    let j = hi + 1;
    
    while (true) {
        // Move i right until element >= pivot
        do {
            i++;
        } while (arr[i] < pivot);
        
        // Move j left until element <= pivot
        do {
            j--;
        } while (arr[j] > pivot);
        
        // If pointers crossed, partition is done
        if (i >= j) {
            return j;
        }
        
        // Swap elements on wrong sides
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}
 
// Quicksort using Hoare partition
function quicksortHoare(
    arr: number[],
    lo: number = 0,
    hi: number = arr.length - 1
): void {
    if (lo < hi) {
        const p = hoarePartition(arr, lo, hi);
        quicksortHoare(arr, lo, p);      // Note: include p
        quicksortHoare(arr, p + 1, hi);
    }
}

Lomuto vs Hoare Partition
Aspect	Lomuto	Hoare
Simplicity	Easier to understand	More complex
Swaps	More (O(n) in worst case)	Fewer (~n/6 average)
Pivot Position	Ends up at partition point	May not be at partition point
Duplicates	Degrades with many duplicates	Also degrades
Cache	Good locality	Good locality

Dutch National Flag: Three-Way Partition

The Dutch National Flag problem (named by Edsger Dijkstra after the three-colored Dutch flag) extends partitioning to three categories:

Problem: Given an array with elements in just three distinct values (say 0, 1, 2), sort it in-place with O(1) space.

Real applications:

Sorting colors, priorities, or categories
Three-way partition in quicksort (handles duplicates)
Separating negatives, zeros, positives

The Algorithm:

Maintain three regions:

[0, low): All 0s (red)
[low, mid): All 1s (white)
(high, n): All 2s (blue)

dutchNationalFlag.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Dutch National Flag algorithm.
 * Sort array with values {0, 1, 2} in-place.
 * 
 * Invariants maintained:
 * - arr[0..low-1]     = 0 (all zeros)
 * - arr[low..mid-1]   = 1 (all ones)
 * - arr[mid..high]    = unexplored
 * - arr[high+1..n-1]  = 2 (all twos)
 * 
 * Time:  O(n) — single pass
 * Space: O(1) — three pointers only
 */
function dutchNationalFlag(arr: number[]): void {
    let low = 0;              // Next position for 0
    let mid = 0;              // Current element being examined
    let high = arr.length - 1; // Next position for 2
    
    while (mid <= high) {
        if (arr[mid] === 0) {
            // Move 0 to the low region
            [arr[low], arr[mid]] = [arr[mid], arr[low]];
            low++;
            mid++;
        } else if (arr[mid] === 1) {
            // 1 is in correct region, just advance
            mid++;
        } else {
            // arr[mid] === 2: Move to high region
            [arr[mid], arr[high]] = [arr[high], arr[mid]];
            high--;
            // Note: Don't increment mid! The swapped element is unexplored.
        }
    }
}
 
// Example
const colors = [2, 0, 2, 1, 1, 0, 1, 2, 0, 1];
dutchNationalFlag(colors);
console.log(colors); 
// [0, 0, 0, 1, 1, 1, 1, 2, 2, 2]

Trace Example:

Initial: [2, 0, 2, 1, 1, 0]
         low=0, mid=0, high=5

mid=0: arr[0]=2 → swap with high → [0, 0, 2, 1, 1, 2], high=4
mid=0: arr[0]=0 → swap with low  → [0, 0, 2, 1, 1, 2], low=1, mid=1
mid=1: arr[1]=0 → swap with low  → [0, 0, 2, 1, 1, 2], low=2, mid=2
mid=2: arr[2]=2 → swap with high → [0, 0, 1, 1, 2, 2], high=3
mid=2: arr[2]=1 → just advance   → mid=3
mid=3: arr[3]=1 → just advance   → mid=4
mid=4 > high=3: STOP

Result: [0, 0, 1, 1, 2, 2]

Critical Detail

When swapping with high, do NOT increment mid. The element swapped from high is unexplored—it could be 0, 1, or 2. We must examine it before moving on. This is the most common bug in implementations.

Application: Three-Way Quicksort Partition

When the array has many duplicates, standard quicksort degrades. Three-way partition handles this by separating elements into three groups: < pivot, = pivot, > pivot.

threeWayPartition.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Three-way partition for quicksort (handles duplicates well).
 * 
 * Partitions arr[lo..hi] into three regions:
 * - arr[lo..lt-1]    < pivot
 * - arr[lt..gt]      = pivot
 * - arr[gt+1..hi]    > pivot
 * 
 * @returns [lt, gt] — boundaries of the pivot region
 */
function threeWayPartition(
    arr: number[],
    lo: number,
    hi: number
): [number, number] {
    const pivot = arr[lo];
    let lt = lo;  // Less than boundary
    let gt = hi;  // Greater than boundary
    let i = lo + 1;
    
    while (i <= gt) {
        if (arr[i] < pivot) {
            [arr[lt], arr[i]] = [arr[i], arr[lt]];
            lt++;
            i++;
        } else if (arr[i] > pivot) {
            [arr[i], arr[gt]] = [arr[gt], arr[i]];
            gt--;
        } else {
            i++;
        }
    }
    
    return [lt, gt];
}
 
// Three-way quicksort
function quicksort3Way(
    arr: number[],
    lo: number = 0,
    hi: number = arr.length - 1
): void {
    if (lo >= hi) return;
    
    const [lt, gt] = threeWayPartition(arr, lo, hi);
    quicksort3Way(arr, lo, lt - 1);  // Sort elements < pivot
    quicksort3Way(arr, gt + 1, hi);  // Sort elements > pivot
    // Elements = pivot are already in place!
}

Removing Duplicates In-Place

Problem: Given a sorted array, remove duplicates in-place such that each element appears only once. Return the new length.

This is a classic interview problem (LeetCode 26) that demonstrates the read-write pointer pattern.

removeDuplicates.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Remove duplicates from sorted array in-place.
 * 
 * Uses two pointers:
 * - 'write': Next position to write unique element
 * - 'read': Current position being examined
 * 
 * Time:  O(n)
 * Space: O(1)
 * 
 * @returns New length of array with duplicates removed
 */
function removeDuplicates(nums: number[]): number {
    if (nums.length === 0) return 0;
    
    let write = 1; // Position 0 is always kept
    
    for (let read = 1; read < nums.length; read++) {
        if (nums[read] !== nums[write - 1]) {
            // Found new unique element
            nums[write] = nums[read];
            write++;
        }
    }
    
    return write;
}
 
// Example
const arr = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
const newLength = removeDuplicates(arr);
console.log(newLength);              // 5
console.log(arr.slice(0, newLength)); // [0, 1, 2, 3, 4]

Variation: Allow At Most K Duplicates

A harder variant (LeetCode 80): allow each element to appear at most twice (or k times).

removeDuplicatesK.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Remove duplicates allowing at most k occurrences.
 * 
 * Key insight: Compare with element k positions back.
 * If different, it's safe to write.
 */
function removeDuplicatesK(nums: number[], k: number): number {
    if (nums.length <= k) return nums.length;
    
    let write = k; // First k elements always kept
    
    for (let read = k; read < nums.length; read++) {
        // Compare with element k positions before write pointer
        if (nums[read] !== nums[write - k]) {
            nums[write] = nums[read];
            write++;
        }
    }
    
    return write;
}
 
// Example: Allow at most 2 duplicates
const arr = [1, 1, 1, 2, 2, 2, 3];
const len = removeDuplicatesK(arr, 2);
console.log(arr.slice(0, len)); // [1, 1, 2, 2, 3]

Read-Write Pointer Pattern

Many in-place problems use this pattern: a 'read' pointer scans forward examining elements, while a 'write' pointer trails behind, marking where to place elements that pass some filter. The gap between them represents filtered-out elements.

Move Zeros and Remove Element

Two related problems that use the same read-write pattern:

Move Zeros: Move all zeros to the end while maintaining relative order of non-zeros.

Remove Element: Remove all occurrences of a value, return new length.

moveZeros.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Move all zeros to the end of the array.
 * Maintain relative order of non-zero elements.
 * 
 * Time:  O(n)
 * Space: O(1)
 */
function moveZeroes(nums: number[]): void {
    let write = 0;
    
    // First pass: move all non-zeros to front
    for (let read = 0; read < nums.length; read++) {
        if (nums[read] !== 0) {
            nums[write] = nums[read];
            write++;
        }
    }
    
    // Second pass: fill remaining with zeros
    while (write < nums.length) {
        nums[write] = 0;
        write++;
    }
}
 
// Alternative: Single pass with swapping
function moveZeroesSinglePass(nums: number[]): void {
    let lastNonZero = 0;
    
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== 0) {
            [nums[lastNonZero], nums[i]] = [nums[i], nums[lastNonZero]];
            lastNonZero++;
        }
    }
}
 
// Example
const arr = [0, 1, 0, 3, 12];
moveZeroes(arr);
console.log(arr); // [1, 3, 12, 0, 0]

removeElement.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Remove all occurrences of 'val' from array in-place.
 * 
 * Time:  O(n)
 * Space: O(1)
 * 
 * @returns New length after removal
 */
function removeElement(nums: number[], val: number): number {
    let write = 0;
    
    for (let read = 0; read < nums.length; read++) {
        if (nums[read] !== val) {
            nums[write] = nums[read];
            write++;
        }
    }
    
    return write;
}
 
// When removal is rare, swap with end (fewer writes)
function removeElementOptimized(nums: number[], val: number): number {
    let i = 0;
    let n = nums.length;
    
    while (i < n) {
        if (nums[i] === val) {
            nums[i] = nums[n - 1];
            n--;
        } else {
            i++;
        }
    }
    
    return n;
}

Fisher-Yates Shuffle: Randomizing In-Place

The Fisher-Yates shuffle (also called Knuth shuffle) generates a uniformly random permutation of an array in-place. It's the gold standard for shuffling—simple, efficient, and provably uniform.

Applications:

Card game shuffling
A/B test randomization
Generating random samples
Playlist shuffling
Monte Carlo simulations

fisherYates.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Fisher-Yates shuffle: Generate uniformly random permutation.
 * 
 * Algorithm:
 * For i from n-1 down to 1:
 *   Pick random j from [0, i]
 *   Swap arr[i] with arr[j]
 * 
 * Time:  O(n)
 * Space: O(1)
 * 
 * Proof of uniformity:
 * Each element has 1/n probability of ending in any position.
 * The algorithm generates all n! permutations with equal probability.
 */
function shuffle(arr: number[]): void {
    for (let i = arr.length - 1; i > 0; i--) {
        // Random index from 0 to i (inclusive)
        const j = Math.floor(Math.random() * (i + 1));
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}
 
// Alternative: Forward version
function shuffleForward(arr: number[]): void {
    for (let i = 0; i < arr.length - 1; i++) {
        // Random index from i to n-1 (inclusive)
        const j = i + Math.floor(Math.random() * (arr.length - i));
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}
 
// Example
const deck = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
shuffle(deck);
console.log(deck); // e.g., [7, 2, 10, 4, 1, 3, 9, 5, 8, 6]

Common Shuffling Bug

A common mistake is picking j from [0, n-1] instead of [0, i]. This produces a non-uniform distribution! Some permutations become more likely than others. Always use the correct range for true randomness.

Proof of Correctness:

To show all n! permutations are equally likely:

The first element can go to any of n positions
The second can go to any of remaining n-1 positions
And so on...

Total: n × (n-1) × (n-2) × ... × 1 = n! equally likely outcomes.

Each permutation P has probability:

P(arr[n-1] is correct) × P(arr[n-2] is correct | arr[n-1]) × ...
= 1/n × 1/(n-1) × 1/(n-2) × ... × 1/1
= 1/n!

Rearranging by Sign: Alternating Patterns

Problem: Rearrange array with alternating positive and negative numbers, maintaining relative order within each group.

This combines partitioning with interleaving—a more complex in-place transformation.

rearrangeBySign.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * Rearrange array with alternating positive and negative.
 * Assume equal number of positive and negative elements.
 * 
 * Not fully in-place (O(n) for simplicity), but demonstrates the pattern.
 */
function rearrangeBySign(nums: number[]): number[] {
    const pos: number[] = [];
    const neg: number[] = [];
    
    for (const num of nums) {
        if (num > 0) {
            pos.push(num);
        } else {
            neg.push(num);
        }
    }
    
    const result: number[] = [];
    for (let i = 0; i < pos.length; i++) {
        result.push(pos[i]);
        result.push(neg[i]);
    }
    
    return result;
}
 
/**
 * True in-place solution (O(1) extra space) is complex.
 * Key idea: Use sign of numbers to encode visited state,
 * or use rotation-based approach for interleaving.
 */
function rearrangeBySignInPlace(nums: number[]): void {
    // This is a simplified version for demonstration
    // Full in-place O(n) solution requires careful rotation
    
    // Find first wrong position and fix iteratively
    let posIdx = 0; // Next expected positive position (even)
    let negIdx = 1; // Next expected negative position (odd)
    const n = nums.length;
    
    while (posIdx < n && negIdx < n) {
        // Find wrongly placed positive (at odd index)
        while (posIdx < n && nums[posIdx] > 0) {
            posIdx += 2;
        }
        
        // Find wrongly placed negative (at even index)
        while (negIdx < n && nums[negIdx] < 0) {
            negIdx += 2;
        }
        
        if (posIdx < n && negIdx < n) {
            [nums[posIdx], nums[negIdx]] = [nums[negIdx], nums[posIdx]];
        }
    }
}
 
// Example
console.log(rearrangeBySign([3, 1, -2, -5, 2, -4]));
// [3, -2, 1, -5, 2, -4]

Next Permutation: Lexicographic Ordering

Problem: Rearrange array to the next lexicographically greater permutation. If already the largest, rearrange to smallest (wrap around).

This is a classic in-place problem that combines multiple techniques: finding the right position to modify, finding the right swap partner, and reversing a suffix.

Algorithm:

Find largest index i such that nums[i] < nums[i+1] (rightmost "ascent")
Find largest index j > i such that nums[i] < nums[j]
Swap nums[i] and nums[j]
Reverse the suffix starting at i+1

nextPermutation.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Rearrange to next lexicographically greater permutation.
 * Modifies array in-place.
 * 
 * Time:  O(n)
 * Space: O(1)
 */
function nextPermutation(nums: number[]): void {
    const n = nums.length;
    
    // Step 1: Find rightmost ascent (nums[i] < nums[i+1])
    let i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    
    if (i >= 0) {
        // Step 2: Find rightmost element larger than nums[i]
        let j = n - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        
        // Step 3: Swap
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    
    // Step 4: Reverse suffix starting at i+1
    let left = i + 1;
    let right = n - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
}
 
// Examples
const a = [1, 2, 3];
nextPermutation(a);
console.log(a); // [1, 3, 2]
 
const b = [3, 2, 1];
nextPermutation(b);
console.log(b); // [1, 2, 3] (wrapped around)
 
const c = [1, 1, 5];
nextPermutation(c);
console.log(c); // [1, 5, 1]

Why This Works:

[1, 5, 8, 4, 7, 6, 5, 3, 1]
          ↑
          i (4 < 7, rightmost ascent)

Everything after i is in descending order (already "maxed out")
To get next permutation, we need to increment nums[i]
Find smallest element greater than 4 in the suffix: 5
Swap: [1, 5, 8, 5, 7, 6, 4, 3, 1]
Suffix is still descending → reverse to make it ascending (smallest)
Result: [1, 5, 8, 5, 1, 3, 4, 6, 7]

Summary: In-Place Transformation Mastery

In-place array transformations represent the pinnacle of space-efficient algorithm design. Let's consolidate the key patterns and techniques:

Key Takeaways

•Partition is fundamental: Separating elements into groups is the basis for quicksort, Dutch National Flag, and many rearrangement problems.
•Dutch National Flag extends to three groups: The one-pass algorithm handles three-way partitions with O(1) space, essential when duplicates are common.
•Read-write pointers filter elements: One pointer reads, another writes; the gap represents filtered elements. Used in remove duplicates, move zeros, etc.
•Fisher-Yates is the correct shuffle: Always pick from [0, i] not [0, n-1]. This ensures uniform distribution of all n! permutations.
•Next permutation combines techniques: Finding pivots, swapping, and reversing—all in-place—to generate lexicographic sequences.
•Invariants make algorithms correct: At each step, maintain clear invariants about what's processed and what's not. This prevents bugs and proves correctness.

Module Complete:

With this page, you've completed Module 8: Common Array Patterns & Problem Types. You now have a comprehensive mental library of array techniques:

Prefix Sums — O(1) range queries
Kadane's Algorithm — Maximum subarray in O(n)
Rotation & Reversal — Transformation primitives
Merge Operations — Combining sorted sequences
In-Place Transformations — O(1) space manipulation

These patterns appear in countless problems. Recognition is the first step; mastery comes through practice.

Module Complete

You've mastered the essential array patterns that form the backbone of algorithmic problem-solving. These techniques—prefix sums, Kadane's, rotation, merging, and in-place transformations—will serve you throughout your career, from solving interview problems to building production systems.