Common Array Patterns for Coding Interviews: Kadane’s, Dutch National Flag, and Rotation

Three in-place array patterns for coding interviews: Kadane's algorithm, the Dutch National Flag partition and rotation by reversal, each built on one clear invariant.

Executive Summary: Three array patterns for coding interviews cover a large share of in-place questions: Kadane’s algorithm for the best subarray sum, the Dutch National Flag partition for grouping values, and reversal for rotation. Each runs in O(n) time with O(1) extra space and depends on one invariant. A wrong invariant fails on all-negative input, swapped elements, or large k.
Array patterns for coding interviews: Kadane scan, three-way partition pointers, and rotation by reversal

A candidate writes a maximum subarray solution that starts with best = 0. It passes every sample, then fails the one hidden test where every number is negative. The loop is correct. The starting value is wrong, and the invariant it was supposed to protect was never stated.

Array patterns for coding interviews are small, reusable in-place techniques that turn a scan over an array into a proof. An invariant is a statement that stays true before and after every loop step. A subarray is a contiguous slice of an array, so [2, -1, 5] is a subarray of [3, 2, -1, 5], while [3, 5] is not. In-place means the algorithm uses O(1) extra space beyond the input.

The code targets Python 3.12 and Java 21. Big-O notation describes how running time grows with input size, and every bound below names its case. If you want the memory model behind arrays first, see the guide to arrays and their operation costs.

My position: memorizing three solutions is the wrong way to prepare. Memorize three invariants. Kadane’s invariant is “best sum of a subarray ending here”. The flag invariant is “three labeled zones plus one unknown zone”. The rotation invariant is “reversing twice restores order”. If you can say the invariant, you can rebuild the code in a minute and debug it when it fails.

How to recognize when you need array patterns for coding interviews

Each pattern has a recognizable question shape. Learn the signals, not the problem names.

  • “Best contiguous run.” Maximum sum of a subarray, with negatives allowed. That signals Kadane’s algorithm.
  • “Group values in place.” Sort an array that holds only three distinct values, or put smaller items before a pivot. That signals a three-way partition.
  • “Shift everything by k.” Rotate an array right by k positions without a second array. That signals reversal or cyclic replacement.
  • “O(1) extra space.” This phrase rules out copying and pushes you toward swaps and pointers.
  • Constraints around 10^5 or 10^6. An O(n^2) pair scan will time out, so a single pass is expected.

The same signals separate these patterns from neighbors. A fixed-length run points to fixed-size window updates. Repeated range totals point to range sums with prefix arrays.

Kadane’s algorithm: the best subarray sum

The problem in plain words: given integers that may be negative, find the contiguous slice with the largest total. For [3, -4, 2, -1, 5, -6, 2] the answer is 6, from the slice [2, -1, 5].

Brute force first

Try every start index, extend the end index one step at a time, and keep a running sum. That is two nested loops, so O(n^2) time in the worst case and O(1) space. At n = 10^5 it means about five billion additions, which is a time limit exceeded.

The insight and the invariant

Any best subarray ends at some index. So ask a smaller question at each index i: what is the best sum of a subarray that ends exactly at i? Call it cur. Either that subarray is just nums[i], or it extends the best one ending at i - 1. Extending helps only when the previous cur is positive.

The recurrence is cur = max(nums[i], cur + nums[i]). The answer is the largest cur seen at any index. The invariant: after step i, cur is the best sum ending at i, and best is the best over all indices up to i.

index :   0    1    2    3    4    5    6
nums  :   3   -4    2   -1    5   -6    2
cur   :   3   -1    2    1    6    0    2
best  :   3    3    3    3    6    6    6

                  [ 2  -1   5 ]  = 6  (indices 2 to 4)

The all-negative trap

Many people initialize best to zero because “the answer is at least zero”. That quietly allows an empty subarray, which is a different problem.

# WRONG: best starts at 0, so an all-negative array returns 0
def max_subarray_wrong(nums: list[int]) -> int:
    best = cur = 0
    for x in nums:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

On [-3, -1, -2] this returns 0, but the best non-empty subarray is [-1] with sum -1. The fix is to seed both variables with the first element and start the loop at index 1.

Implementation with index recovery

Interviewers often ask for the slice, not only the sum. Track where the current run started, and copy that start into the best record whenever the best improves. In Python, with the brute force kept as a cross-check:

def max_subarray(nums: list[int]) -> tuple[int, int, int]:
    """Return (best_sum, left, right) for a non-empty list, right inclusive."""
    if not nums:
        raise ValueError("nums must not be empty")
    best = cur = nums[0]
    best_l = cur_l = best_r = 0
    for i in range(1, len(nums)):
        if cur < 0:            # a negative prefix only hurts: restart here
            cur = nums[i]
            cur_l = i
        else:
            cur += nums[i]
        if cur > best:
            best, best_l, best_r = cur, cur_l, i
    return best, best_l, best_r


def max_subarray_brute(nums: list[int]) -> int:
    best = nums[0]
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            best = max(best, total)
    return best


if __name__ == "__main__":
    assert max_subarray([3, -4, 2, -1, 5, -6, 2]) == (6, 2, 4)
    assert max_subarray([-3, -1, -2]) == (-1, 1, 1)     # all negative
    assert max_subarray([7]) == (7, 0, 0)                # single element
    assert max_subarray([2, 2, 2]) == (6, 0, 2)          # duplicates
    assert max_subarray([0, 0]) == (0, 0, 0)
    assert max_subarray([-1, -1]) == (-1, 0, 0)
    try:
        max_subarray([])
        raise AssertionError("expected ValueError")
    except ValueError:
        pass
    for case in ([3, -4, 2, -1, 5, -6, 2], [-3, -1, -2], [5, -9, 6], [1, -1, 1, -1]):
        total, left, right = max_subarray(case)
        assert total == max_subarray_brute(case) == sum(case[left:right + 1])
    print("kadane tests passed")

The same algorithm in Java:

public class KadaneDemo {

    static int[] maxSubarray(int[] nums) {
        if (nums.length == 0) throw new IllegalArgumentException("nums must not be empty");
        int best = nums[0];
        int cur = nums[0];
        int bestL = 0;
        int curL = 0;
        int bestR = 0;
        for (int i = 1; i < nums.length; i++) {
            if (cur < 0) {
                cur = nums[i];
                curL = i;
            } else {
                cur += nums[i];
            }
            if (cur > best) {
                best = cur;
                bestL = curL;
                bestR = i;
            }
        }
        return new int[] {best, bestL, bestR};
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        check(java.util.Arrays.equals(maxSubarray(new int[] {3, -4, 2, -1, 5, -6, 2}), new int[] {6, 2, 4}), "basic");
        check(java.util.Arrays.equals(maxSubarray(new int[] {-3, -1, -2}), new int[] {-1, 1, 1}), "all negative");
        check(java.util.Arrays.equals(maxSubarray(new int[] {7}), new int[] {7, 0, 0}), "single");
        check(java.util.Arrays.equals(maxSubarray(new int[] {2, 2, 2}), new int[] {6, 0, 2}), "duplicates");
        boolean threw = false;
        try {
            maxSubarray(new int[] {});
        } catch (IllegalArgumentException e) {
            threw = true;
        }
        check(threw, "empty throws");
        System.out.println("PASS");
    }
}

Dry-run trace

Input [3, -4, 2, -1, 5, -6, 2]. The columns show the state after each index.

i nums[i] Action cur cur_l best best range
0 3 seed 3 0 3 0 to 0
1 -4 cur is 3, extend -1 0 3 0 to 0
2 2 cur is -1, restart 2 2 3 0 to 0
3 -1 extend 1 2 3 0 to 0
4 5 extend, new best 6 2 6 2 to 4
5 -6 extend 0 2 6 2 to 4
6 2 cur is 0, extend 2 2 6 2 to 4

Time is O(n) in the worst case, one pass. Space is O(1). The brute force is O(n^2) time. Sums can overflow a Java int on large inputs, so use long when values or lengths are big.

A mistake I see often in interviews is the zero seed. The candidate states “the answer is at least zero” without checking whether the question allows an empty subarray. I now ask candidates to test an all-negative array before saying done. The ones who find the bug on their own usually fix it in a single line and move on.

Dutch National Flag: three-way partition in one pass

Edsger Dijkstra posed this as sorting a row of red, white, and blue balls using the colors of the Dutch flag. The interview form: given values below, equal to, and above a pivot, rearrange them in place so that all smaller values come first, then equal values, then larger values. With the pivot 1 and an array holding only 0, 1, and 2, this is a full sort.

Brute force and the two-pass fix

A sort does the job in O(n log n) time. Counting each value and rewriting the array takes O(n) time and two passes. A single-pass, swap-based answer is what interviewers want, and it generalizes to any pivot.

The invariant: three zones and an unknown

Keep three indices, low, mid, and high. They split the array into four zones at every step.

 0          low         mid          high         n-1
 +-----------+-----------+-------------+-----------+
 |  < pivot   | == pivot  |   unknown   |  > pivot   |
 +-----------+-----------+-------------+-----------+
 [0, low)     [low, mid)   [mid, high]    (high, n-1]

The loop runs while mid <= high, so the unknown zone shrinks every step. Look at nums[mid]:

  • Smaller than the pivot: swap it with nums[low], then advance both low and mid. The swapped-in value came from the equal zone, so it is already known.
  • Equal to the pivot: advance mid.
  • Larger than the pivot: swap it with nums[high] and decrease high. Do not advance mid, because the value that arrived from the right end is unknown.

The classic bug

# WRONG: mid advances after swapping with high
else:
    nums[mid], nums[high] = nums[high], nums[mid]
    high -= 1
    mid += 1
# RIGHT: the value swapped in from the right has not been examined
else:
    nums[mid], nums[high] = nums[high], nums[mid]
    high -= 1

Take [1, 2, 0] with pivot 1. The first step moves mid past the 1. At index 1 the value 2 swaps with the 0, giving [1, 0, 2]. The wrong version then skips index 1 and returns [1, 0, 2], with the 0 stranded behind the 1. The right version examines the 0 and swaps it to the front.

Implementation

In Python, written for any pivot value:

def three_way_partition(nums: list[int], pivot: int) -> None:
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        v = nums[mid]
        if v < pivot:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif v == pivot:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1


def is_partitioned(nums: list[int], pivot: int) -> bool:
    i = 0
    while i < len(nums) and nums[i] < pivot:
        i += 1
    while i < len(nums) and nums[i] == pivot:
        i += 1
    return all(x > pivot for x in nums[i:])


if __name__ == "__main__":
    a = [2, 0, 2, 1, 1, 0]
    three_way_partition(a, 1)
    assert a == [0, 0, 1, 1, 2, 2]
    b: list[int] = []
    three_way_partition(b, 1)
    assert b == []
    c = [1]
    three_way_partition(c, 1)
    assert c == [1]
    d = [1, 1, 1]                      # duplicates only
    three_way_partition(d, 1)
    assert d == [1, 1, 1]
    e = [1, 2, 0]                      # the case the wrong version breaks
    three_way_partition(e, 1)
    assert e == [0, 1, 2]
    for case, p in (([5, 1, 9, 1], 4), ([3, 3, 1, 5, 3], 3), ([9, 8, 7], 8)):
        original = sorted(case)
        three_way_partition(case, p)
        assert sorted(case) == original and is_partitioned(case, p)
    print("three way partition tests passed")

The same partition in Java:

import java.util.Arrays;

public class ThreeWayPartitionDemo {

    static void threeWayPartition(int[] nums, int pivot) {
        int low = 0;
        int mid = 0;
        int high = nums.length - 1;
        while (mid <= high) {
            if (nums[mid] < pivot) {
                swap(nums, low, mid);
                low++;
                mid++;
            } else if (nums[mid] == pivot) {
                mid++;
            } else {
                swap(nums, mid, high);
                high--;
            }
        }
    }

    static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        int[] a = {2, 0, 2, 1, 1, 0};
        threeWayPartition(a, 1);
        check(Arrays.equals(a, new int[] {0, 0, 1, 1, 2, 2}), "basic");
        int[] b = {};
        threeWayPartition(b, 1);
        check(b.length == 0, "empty");
        int[] c = {1};
        threeWayPartition(c, 1);
        check(Arrays.equals(c, new int[] {1}), "single");
        int[] d = {1, 1, 1};
        threeWayPartition(d, 1);
        check(Arrays.equals(d, new int[] {1, 1, 1}), "duplicates");
        int[] e = {1, 2, 0};
        threeWayPartition(e, 1);
        check(Arrays.equals(e, new int[] {0, 1, 2}), "swap-in case");
        System.out.println("PASS");
    }
}

Dry-run trace

Input [2, 0, 2, 1, 1, 0] with pivot 1.

Step low mid high nums[mid] Action Array after
1 0 0 5 2 swap with high, high down 0 0 2 1 1 2
2 0 0 4 0 swap with low, both up 0 0 2 1 1 2
3 1 1 4 0 swap with low, both up 0 0 2 1 1 2
4 2 2 4 2 swap with high, high down 0 0 1 1 2 2
5 2 2 3 1 equal, mid up 0 0 1 1 2 2
6 2 3 3 1 equal, mid up 0 0 1 1 2 2

After step 6, mid is 4 and high is 3, so the loop ends. Time is O(n) in the worst case, since every step either advances mid or shrinks high, and each element is swapped at most once into place. Space is O(1). The partition is not stable: equal values may change their relative order.

Rotating an array by k positions

Rotating right by k moves each element k places to the right and wraps the tail to the front. So [1, 2, 3, 4, 5, 6, 7] rotated by 3 becomes [5, 6, 7, 1, 2, 3, 4]. The in-place constraint rules out building a new array.

Reversal: three reversals, no extra space

Reverse the whole array, then reverse the first k items, then reverse the rest. The first reversal puts the last k items at the front, but backwards. The next two reversals fix the order inside each block.

start     : 1 2 3 4 5 6 7
reverse all: 7 6 5 4 3 2 1
reverse [0,3): 5 6 7 | 4 3 2 1
reverse [3,7): 5 6 7 | 1 2 3 4

The step most candidates skip is reducing k first. If k is larger than n, you must use k % n.

# WRONG: slicing with k larger than the length
nums[:] = nums[-k:] + nums[:-k]
# RIGHT: reduce k first
k %= len(nums)
nums[:] = nums[len(nums) - k:] + nums[:len(nums) - k]

With 7 items and k = 10, the wrong slice nums[-10:] clamps to the whole list and nums[:-10] is empty, so nothing moves. The right answer is a rotation by 3. The slice form also builds a new list, so it costs O(n) extra space. The in-place version is below.

In Python, with reversal and the cyclic-replacement alternative:

def reverse_range(nums: list[int], i: int, j: int) -> None:
    while i < j:
        nums[i], nums[j] = nums[j], nums[i]
        i += 1
        j -= 1


def rotate_right(nums: list[int], k: int) -> None:
    n = len(nums)
    if n == 0:
        return
    k %= n
    reverse_range(nums, 0, n - 1)
    reverse_range(nums, 0, k - 1)
    reverse_range(nums, k, n - 1)


def rotate_cyclic(nums: list[int], k: int) -> None:
    n = len(nums)
    if n == 0:
        return
    k %= n
    if k == 0:
        return
    moved = 0
    start = 0
    while moved < n:
        cur = start
        carry = nums[start]
        while True:
            nxt = (cur + k) % n
            nums[nxt], carry = carry, nums[nxt]
            cur = nxt
            moved += 1
            if cur == start:
                break
        start += 1


if __name__ == "__main__":
    a = [1, 2, 3, 4, 5, 6, 7]
    rotate_right(a, 3)
    assert a == [5, 6, 7, 1, 2, 3, 4]
    b = [1, 2, 3, 4, 5, 6, 7]
    rotate_right(b, 10)                # k larger than n
    assert b == [5, 6, 7, 1, 2, 3, 4]
    c = [1, 2, 3]
    rotate_right(c, 0)
    assert c == [1, 2, 3]
    d: list[int] = []
    rotate_right(d, 4)
    assert d == []
    e = [9]
    rotate_right(e, 5)
    assert e == [9]
    f = [1, 1, 2]                      # duplicates
    rotate_right(f, 1)
    assert f == [2, 1, 1]
    for n in range(0, 9):
        for k in range(0, 20):
            x = list(range(n))
            y = list(range(n))
            rotate_right(x, k)
            rotate_cyclic(y, k)
            assert x == y
            if n:
                shift = k % n
                assert x == (list(range(n))[n - shift:] + list(range(n))[:n - shift])
    print("rotation tests passed")

The same reversal rotation in Java:

import java.util.Arrays;

public class RotateDemo {

    static void reverseRange(int[] a, int i, int j) {
        while (i < j) {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
            i++;
            j--;
        }
    }

    static void rotateRight(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) return;
        k %= n;
        reverseRange(nums, 0, n - 1);
        reverseRange(nums, 0, k - 1);
        reverseRange(nums, k, n - 1);
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6, 7};
        rotateRight(a, 3);
        check(Arrays.equals(a, new int[] {5, 6, 7, 1, 2, 3, 4}), "basic");
        int[] b = {1, 2, 3, 4, 5, 6, 7};
        rotateRight(b, 10);
        check(Arrays.equals(b, new int[] {5, 6, 7, 1, 2, 3, 4}), "k larger than n");
        int[] c = {1, 2, 3};
        rotateRight(c, 0);
        check(Arrays.equals(c, new int[] {1, 2, 3}), "k zero");
        int[] d = {};
        rotateRight(d, 4);
        check(d.length == 0, "empty");
        int[] e = {9};
        rotateRight(e, 5);
        check(Arrays.equals(e, new int[] {9}), "single");
        int[] f = {1, 1, 2};
        rotateRight(f, 1);
        check(Arrays.equals(f, new int[] {2, 1, 1}), "duplicates");
        System.out.println("PASS");
    }
}

Cyclic replacement and why it needs several cycles

Cyclic replacement moves each element straight to its final index, (i + k) % n, carrying the displaced value onward. It touches every element exactly once, so it also takes O(n) time. But one trip around may not cover the array. With n = 6 and k = 2, starting at index 0 visits only 0, 2, and 4. The number of separate cycles is the greatest common divisor of n and k, which is why the code counts moved elements instead of assuming one cycle.

Reversal is the version to write in an interview: it has three short loops and no cycle arithmetic. Cyclic replacement moves each element once, where reversal writes each element twice, but the extra writes rarely matter outside micro-optimization.

Dry-run trace for rotation

Step Operation Array after
0 start, n = 7, k = 3 1 2 3 4 5 6 7
1 reverse indices 0 to 6 7 6 5 4 3 2 1
2 reverse indices 0 to 2 5 6 7 4 3 2 1
3 reverse indices 3 to 6 5 6 7 1 2 3 4

Complexity of the three patterns

Pattern Time Extra space Notes
Kadane’s algorithm O(n) worst case O(1) Needs at least one element; brute force is O(n^2)
Three-way partition O(n) worst case, one pass O(1) Not stable; sorting is O(n log n)
Rotation by reversal O(n) worst case, about 2n element writes O(1) Reduce k with k % n first
Rotation by cyclic replacement O(n) worst case, n element writes O(1) gcd(n, k) separate cycles
Rotation by slicing O(n) worst case O(n) Simple, but copies the array

Where this shows up in real systems

  • Quicksort with many duplicate keys. Three-way partitioning is the idea behind “3-way quicksort”, which the Princeton algs4 quicksort notes describe as Dijkstra’s approach. It keeps equal keys out of further recursion, so arrays with many repeats sort faster.
  • Ring buffers and rotating queues. Python’s collections.deque.rotate rotates a deque by n steps, and rotation underlies circular buffers for logs and audio.
  • Time series analysis. Finding the best contiguous gain or loss in a series of daily changes is the maximum subarray problem. The maximum drawdown of a price series uses the same single-pass state idea.
  • Partitioning in data pipelines. Splitting records into below, at, and above a threshold in one pass avoids sorting the whole set.

How to explain it in an interview

  1. Restate and test. Say the problem back and name edge inputs: empty, one element, all negative, duplicates, k larger than n.
  2. Brute force and its bottleneck. Kadane: O(n^2) subarray scan. Flag: sort in O(n log n). Rotation: a second array, O(n) space.
  3. The insight. One sentence per pattern, as in the invariants above.
  4. Code, then trace. Run one small input by hand and narrate the pointers.
  5. Complexity. O(n) time, O(1) space, with the reason: each element is visited a constant number of times.

Expect these follow-ups. “Return the subarray itself” means track the start. “Handle a circular array” means compare the best subarray with the total minus the worst subarray. “Why is the partition unstable?” has a short answer: swaps jump over equal values. A weak answer reproduces the code. A strong answer states the invariant and the input that breaks each shortcut.

Which array pattern fits: a decision framework

  1. Is the answer a contiguous run with a sum or product? Use Kadane’s algorithm if the sum can go negative and the run has no length limit.
  2. Is the run length fixed? Use a window with add-one, remove-one updates instead.
  3. Do you need values grouped around a pivot, in place? Use the three-way partition. For two groups, two pointers are enough, using a read pointer and a write pointer for in-place edits.
  4. Do you need a cyclic shift? Reverse three times, after reducing k modulo n.
  5. Do you need many range totals? Build a prefix array once and answer queries in O(1) each.

When not to use these patterns

  • Kadane’s with all-positive input. The whole array is the answer, and a scan is wasteful. If there is a length constraint or a “no more than k elements” rule, the single-state recurrence no longer holds. Use a window or a prefix-array approach.
  • Partitioning when you need a stable order. The swaps scramble equal elements. Use a stable sort, or a scan into extra buckets, when order within a group matters.
  • In-place rotation of a linked structure or a huge, shared array. Moving elements is wasted work when an offset would do. Keep a start index and read modulo n, as a ring buffer does.

Common mistakes

  • Zero seed in Kadane’s. Starting best at 0 returns 0 for [-3, -1, -2]. Seed with the first element.
  • Losing the start index. Updating cur_l on every restart but copying it to the best record only when the best improves keeps the range correct. Copying it at the wrong time returns a range that does not sum to the answer.
  • Advancing mid after a swap with high. The value from the right is unexamined. Input [1, 2, 0] exposes it.
  • Forgetting k % n. With k = 10 and 7 items, reverse_range(0, k - 1) runs past the end and raises IndexError.
  • Assuming one cycle in cyclic replacement. With n = 6 and k = 2, one cycle moves only half the items. Count moved elements.
  • Integer overflow in Java. A long run of large values overflows an int sum. Use long when the limits are not small.

Practice problems

Problem Difficulty The twist
Maximum Subarray Medium All-negative input and the non-empty rule
Sort Colors Medium Three-way partition with pivot 1, one pass
Rotate Array Medium Reduce k, then three reversals in O(1) space
Best Time to Buy and Sell Stock Easy Kadane’s on daily differences, or a running minimum
Maximum Product Subarray Medium Track both the max and min, since a negative flips them
Wiggle Sort Medium Partition around the median, then interleave
Maximum Sum Circular Subarray Medium Compare Kadane’s best with total minus the worst subarray
Rotate Image Medium Transpose then reverse rows, the same reversal idea in 2D

Key takeaways

  • Say each invariant out loud: best sum ending here, four zones, reverse twice to restore order.
  • Seed Kadane’s with the first element, never with zero, unless the problem allows an empty subarray.
  • Track the start index of the current run to recover the subarray.
  • In a three-way partition, advance mid only when the value you examined is placed in a known zone.
  • Reduce k with k % n before any rotation code, and handle empty arrays first.
  • Reversal is the interview-safe rotation, and cyclic replacement needs gcd(n, k) cycles.
  • All three patterns run in O(n) time with O(1) extra space, and none of them needs sorting.

Frequently Asked Questions

How does Kadane’s algorithm handle an array of all negative numbers?

Seed the running sum and the best sum with the first element instead of zero. The scan then returns the largest single element, because extending a negative run never helps.

What is the Dutch National Flag algorithm used for?

It partitions an array into values below, equal to, and above a pivot in one pass with O(1) extra space. It solves the sort colors problem and speeds up quicksort when many keys are equal.

How do you rotate an array by k positions in place?

Reduce k with k mod n, reverse the whole array, then reverse the first k elements and the remaining elements separately. This takes O(n) time and O(1) extra space.

Is the three-way partition stable?

No. The swaps with the high end can reorder equal elements. If equal items must keep their original order, use a stable sort or collect each group into its own list.

Name the invariant before you write the loop

Kadane’s algorithm, the three-way partition, and rotation by reversal all reduce to one habit: state what is true after every step, then write the smallest loop that keeps it true. The all-negative seed, the skipped swap, and the missing modulo are all invariant violations. For more DSA patterns, see the DSA hub.

Rule of thumb: if you cannot say the invariant in one sentence, you are not ready to write the loop.

Originally posted on 22 November 2026 and post last modified on 22 November 2026

Algorithms Arrays Coding Interviews Dutch National Flag Kadane Algorithm

Share this article

Leave a Reply

Your email address will not be published. Required fields are marked *