ArrayProblem 32 of 36

Three way partitioning of an array around a given value

Brute Force
Time: O(n log n)
Space: O(n)
Optimal
Time: O(n)
Space: O(1)

Problem Statement

Given an array and a range [lowVal, highVal], partition the array around this range such that:

  1. All elements smaller than lowVal come first
  2. All elements in the range [lowVal, highVal] come next
  3. All elements greater than highVal come last

The relative order within each partition doesn't matter.

Example:

  • Input: arr = [1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32], lowVal = 14, highVal = 20
  • Output: [1, 5, 4, 2, 3, 1, 14, 20, 20, 54, 87, 98, 32]
  • Explanation: Elements < 14 first, then 14-20, then > 20.

Approach 1: Brute Force (Sorting-based)

Intuition

Separate elements into three arrays based on the range, then concatenate them.

Algorithm

  1. Create three separate arrays for each partition
  2. Traverse original array and place elements in appropriate partition
  3. Concatenate the three arrays
java
import java.util.*;

public class Solution {
    public void threeWayPartition(int[] arr, int lowVal, int highVal) {
        List<Integer> smaller = new ArrayList<>();
        List<Integer> inRange = new ArrayList<>();
        List<Integer> greater = new ArrayList<>();
        
        for (int num : arr) {
            if (num < lowVal) {
                smaller.add(num);
            } else if (num > highVal) {
                greater.add(num);
            } else {
                inRange.add(num);
            }
        }
        
        // Reconstruct array
        int idx = 0;
        for (int num : smaller) arr[idx++] = num;
        for (int num : inRange) arr[idx++] = num;
        for (int num : greater) arr[idx++] = num;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Single pass through array
  • Space Complexity: O(n) - Three auxiliary arrays

Approach 2: Optimal - Dutch National Flag Algorithm

Intuition

Use three pointers similar to Dutch National Flag problem. Maintain pointers for the boundary of each partition and swap elements in-place.

Algorithm

  1. Initialize three pointers: start = 0, mid = 0, end = n-1
  2. While mid <= end:
    • If arr[mid] < lowVal: swap with start, increment both
    • If arr[mid] > highVal: swap with end, decrement end
    • Else (in range): just increment mid
java
public class Solution {
    public void threeWayPartition(int[] arr, int lowVal, int highVal) {
        int n = arr.length;
        int start = 0;      // Boundary for elements < lowVal
        int mid = 0;        // Current element
        int end = n - 1;    // Boundary for elements > highVal
        
        while (mid <= end) {
            if (arr[mid] < lowVal) {
                swap(arr, start, mid);
                start++;
                mid++;
            } else if (arr[mid] > highVal) {
                swap(arr, mid, end);
                end--;
                // Don't increment mid, need to check swapped element
            } else {
                // Element is in range [lowVal, highVal]
                mid++;
            }
        }
    }
    
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Single pass through array
  • Space Complexity: O(1) - In-place partitioning

Variation: Three-Way Partition with Single Pivot

Intuition

Partition array into three parts: elements less than pivot, equal to pivot, and greater than pivot.

java
public class Solution {
    public void threeWayPartition(int[] arr, int pivot) {
        int n = arr.length;
        int low = 0;
        int mid = 0;
        int high = n - 1;
        
        while (mid <= high) {
            if (arr[mid] < pivot) {
                swap(arr, low, mid);
                low++;
                mid++;
            } else if (arr[mid] > pivot) {
                swap(arr, mid, high);
                high--;
            } else {
                mid++;
            }
        }
    }
    
    // Returns indices of the partition boundaries
    public int[] threeWayPartitionWithIndices(int[] arr, int pivot) {
        int n = arr.length;
        int low = 0;
        int mid = 0;
        int high = n - 1;
        
        while (mid <= high) {
            if (arr[mid] < pivot) {
                swap(arr, low, mid);
                low++;
                mid++;
            } else if (arr[mid] > pivot) {
                swap(arr, mid, high);
                high--;
            } else {
                mid++;
            }
        }
        
        return new int[]{low, high};
    }
    
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Single pass through array
  • Space Complexity: O(1) - In-place partitioning

Key Takeaways

  1. Dutch National Flag Algorithm - Classic three-way partitioning technique
  2. Three pointers - low, mid (current), high maintain partition boundaries
  3. Don't increment mid when swapping with high - The swapped element needs to be checked
  4. Applications - QuickSort optimization, sorting 0s/1s/2s, range partitioning
  5. Invariant - Elements in [0, low) < pivot, [low, mid) == pivot range, (high, n) > pivot
Previous
Smallest Subarray with sum greater than a given value
Next
Minimum swaps required bring elements less equal K together