[AlgoMastery]
Topics›Array›Array Partitioning
📖

Array Partitioning

Array
~20 min read
5 practice problems

Overview

Array Partitioning involves dividing an array into segments based on a condition or property. Elements are rearranged so that elements satisfying the condition appear before (or after) those that don't, often in-place.

The key insight: use two pointers or multiple pointers to separate elements into different regions. This is fundamental to algorithms like Quick Sort and many optimization problems.

Array partitioning is particularly useful for:

  • Partitioning around a pivot
  • Separating elements by property
  • Quick select algorithm
  • Dutch National Flag problem
  • Grouping elements
  • In-place reorganization

Pattern 1: Partition Around Pivot

Partition array so elements < pivot come before elements >= pivot.

function partition(nums: number[], pivot: number): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    while (left <= right && nums[left] < pivot) left++;
    while (left <= right && nums[right] >= pivot) right--;
    
    if (left <= right) {
      [nums[left], nums[right]] = [nums[right], nums[left]];
      left++;
      right--;
    }
  }
  
  return left; // Index where partition occurs
}

Time: O(n), Space: O(1)

Lomuto partition (used in Quick Sort):

function lomutoPartition(nums: number[], left: number, right: number): number {
  const pivot = nums[right];
  let i = left;
  
  for (let j = left; j < right; j++) {
    if (nums[j] <= pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
  }
  
  [nums[i], nums[right]] = [nums[right], nums[i]];
  return i;
}

Time: O(n), Space: O(1)

Pattern 2: Dutch National Flag (Three-Way Partition)

Partition into three regions: < pivot, = pivot, > pivot.

function threeWayPartition(nums: number[], pivot: number): void {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;
  
  while (mid <= high) {
    if (nums[mid] < pivot) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === pivot) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
}

Time: O(n), Space: O(1)

Sort Colors:

function sortColors(nums: number[]): void {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;
  
  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
}

Time: O(n), Space: O(1)

Pattern 3: Partition by Parity

Move all even numbers before odd numbers.

function partitionByParity(nums: number[]): void {
  let left = 0;
  let right = nums.length - 1;
  
  while (left < right) {
    while (left < right && nums[left] % 2 === 0) left++;
    while (left < right && nums[right] % 2 === 1) right--;
    
    if (left < right) {
      [nums[left], nums[right]] = [nums[right], nums[left]];
      left++;
      right--;
    }
  }
}

Time: O(n), Space: O(1)

Maintain relative order:

function partitionByParityStable(nums: number[]): number[] {
  const evens: number[] = [];
  const odds: number[] = [];
  
  for (const num of nums) {
    if (num % 2 === 0) {
      evens.push(num);
    } else {
      odds.push(num);
    }
  }
  
  return [...evens, ...odds];
}

Time: O(n), Space: O(n)

Pattern 4: Partition Array into Disjoint Intervals

Partition so left subarray max <= right subarray min.

function partitionDisjoint(nums: number[]): number {
  const n = nums.length;
  const maxLeft = new Array(n).fill(0);
  const minRight = new Array(n).fill(0);
  
  maxLeft[0] = nums[0];
  for (let i = 1; i < n; i++) {
    maxLeft[i] = Math.max(maxLeft[i - 1], nums[i]);
  }
  
  minRight[n - 1] = nums[n - 1];
  for (let i = n - 2; i >= 0; i--) {
    minRight[i] = Math.min(minRight[i + 1], nums[i]);
  }
  
  for (let i = 0; i < n - 1; i++) {
    if (maxLeft[i] <= minRight[i + 1]) {
      return i + 1;
    }
  }
  
  return n;
}

Time: O(n), Space: O(n)

Pattern 5: Partition Labels

Partition string into as many parts as possible with unique characters.

function partitionLabels(s: string): number[] {
  const lastIndex = new Map<string, number>();
  
  // Record last occurrence of each character
  for (let i = 0; i < s.length; i++) {
    lastIndex.set(s[i], i);
  }
  
  const result: number[] = [];
  let start = 0;
  let end = 0;
  
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, lastIndex.get(s[i])!);
    
    if (i === end) {
      result.push(end - start + 1);
      start = i + 1;
    }
  }
  
  return result;
}

Time: O(n), Space: O(1) for alphabet size

Pattern 6: Kth Largest Element (Quick Select)

Find kth largest element using partitioning.

function findKthLargest(nums: number[], k: number): number {
  return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}

function quickSelect(nums: number[], left: number, right: number, k: number): number {
  if (left === right) return nums[left];
  
  const pivotIndex = lomutoPartition(nums, left, right);
  
  if (k === pivotIndex) {
    return nums[k];
  } else if (k < pivotIndex) {
    return quickSelect(nums, left, pivotIndex - 1, k);
  } else {
    return quickSelect(nums, pivotIndex + 1, right, k);
  }
}

function lomutoPartition(nums: number[], left: number, right: number): number {
  const pivot = nums[right];
  let i = left;
  
  for (let j = left; j < right; j++) {
    if (nums[j] <= pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
  }
  
  [nums[i], nums[right]] = [nums[right], nums[i]];
  return i;
}

Time: O(n) average, O(n²) worst, Space: O(1)

Pattern 7: Partition Array According to Given Pivot

Partition so elements < pivot come before = pivot, which come before > pivot.

function pivotArray(nums: number[], pivot: number): number[] {
  const less: number[] = [];
  const equal: number[] = [];
  const greater: number[] = [];
  
  for (const num of nums) {
    if (num < pivot) {
      less.push(num);
    } else if (num === pivot) {
      equal.push(num);
    } else {
      greater.push(num);
    }
  }
  
  return [...less, ...equal, ...greater];
}

// In-place version
function pivotArrayInPlace(nums: number[], pivot: number): void {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;
  
  while (mid <= high) {
    if (nums[mid] < pivot) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === pivot) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
}

Time: O(n), Space: O(n) or O(1) in-place

Pattern 8: Partition Equal Subset Sum

Check if array can be partitioned into two subsets with equal sum.

function canPartition(nums: number[]): boolean {
  const sum = nums.reduce((a, b) => a + b, 0);
  
  if (sum % 2 !== 0) return false;
  
  const target = sum / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  
  for (const num of nums) {
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }
  
  return dp[target];
}

Time: O(n * sum), Space: O(sum)

DP approach: 0/1 knapsack problem.

Pattern 9: Partition Array for Maximum Sum

Partition array into at most K parts, maximize sum.

function maxSumAfterPartitioning(arr: number[], k: number): number {
  const n = arr.length;
  const dp = new Array(n + 1).fill(0);
  
  for (let i = 1; i <= n; i++) {
    let maxVal = 0;
    
    // Try all partition sizes from 1 to k
    for (let j = 1; j <= k && i - j >= 0; j++) {
      maxVal = Math.max(maxVal, arr[i - j]);
      dp[i] = Math.max(dp[i], dp[i - j] + maxVal * j);
    }
  }
  
  return dp[n];
}

Time: O(n * k), Space: O(n)

Pattern 10: Partition Array into K Equal Sum Subsets

Check if array can be partitioned into K subsets with equal sum.

function canPartitionKSubsets(nums: number[], k: number): boolean {
  const sum = nums.reduce((a, b) => a + b, 0);
  
  if (sum % k !== 0) return false;
  
  const target = sum / k;
  const used = new Array(nums.length).fill(false);
  
  return backtrack(nums, used, 0, 0, k, target);
}

function backtrack(
  nums: number[],
  used: boolean[],
  start: number,
  currentSum: number,
  k: number,
  target: number
): boolean {
  if (k === 1) return true;
  
  if (currentSum === target) {
    return backtrack(nums, used, 0, 0, k - 1, target);
  }
  
  for (let i = start; i < nums.length; i++) {
    if (!used[i] && currentSum + nums[i] <= target) {
      used[i] = true;
      if (backtrack(nums, used, i + 1, currentSum + nums[i], k, target)) {
        return true;
      }
      used[i] = false;
    }
  }
  
  return false;
}

Time: O(k * 2^n), Space: O(n)

Backtracking approach.

Pattern 11: Partition Array into Minimum Number of Deci-Binary Numbers

Find minimum number of deci-binary numbers that sum to n.

function minPartitions(n: string): number {
  let maxDigit = 0;
  
  for (const char of n) {
    maxDigit = Math.max(maxDigit, parseInt(char));
  }
  
  return maxDigit;
}

Time: O(n), Space: O(1)

Explanation: Each digit requires that many deci-binary numbers. Maximum digit determines answer.

Pattern 12: Wiggle Sort II

Partition and rearrange so nums[0] < nums[1] > nums[2] < nums[3]...

function wiggleSort(nums: number[]): void {
  const sorted = [...nums].sort((a, b) => a - b);
  const n = nums.length;
  const mid = Math.floor((n + 1) / 2);
  
  // Interleave smaller and larger halves
  for (let i = 0; i < n; i++) {
    if (i % 2 === 0) {
      nums[i] = sorted[mid - 1 - Math.floor(i / 2)];
    } else {
      nums[i] = sorted[n - 1 - Math.floor(i / 2)];
    }
  }
}

Time: O(n log n), Space: O(n)

When to Use Array Partitioning

Use array partitioning when:

  • Need to separate elements by condition
  • Quick select algorithm (find kth element)
  • In-place reorganization required
  • Dutch National Flag problems
  • Grouping elements by property
  • Optimization problems with constraints

Key principles:

  • Use two or more pointers to mark boundaries
  • Maintain invariants during partitioning
  • Consider stability if order matters

Template (Two-Way Partition)

function partitionTemplate(nums: number[], condition: (num: number) => boolean): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    while (left <= right && condition(nums[left])) left++;
    while (left <= right && !condition(nums[right])) right--;
    
    if (left <= right) {
      [nums[left], nums[right]] = [nums[right], nums[left]];
      left++;
      right--;
    }
  }
  
  return left; // Partition index
}

Template (Three-Way Partition)

function threeWayPartitionTemplate(
  nums: number[],
  lowCondition: (num: number) => boolean,
  highCondition: (num: number) => boolean
): void {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;
  
  while (mid <= high) {
    if (lowCondition(nums[mid])) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (!highCondition(nums[mid])) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
}

Time and Space Complexity Summary

  • Two-way partition: O(n) time, O(1) space
  • Three-way partition: O(n) time, O(1) space
  • Quick select: O(n) avg, O(n²) worst time, O(1) space
  • Partition labels: O(n) time, O(1) space
  • Equal subset sum: O(n * sum) time, O(sum) space
  • K equal subsets: O(k * 2^n) time, O(n) space

Practice Tips

  1. Choose partition type - Two-way vs three-way
  2. Maintain invariants - Keep partitioning conditions true
  3. Pointer management - Update pointers correctly
  4. Stability - Consider if order matters
  5. Edge cases - Empty array, single element, all same

Common Mistakes

  1. Index errors - Off-by-one in pointer updates
  2. Wrong condition - Not maintaining partition invariant
  3. Infinite loops - Not updating pointers
  4. Stability - Not preserving order when needed
  5. Boundary handling - Not handling edge cases

Related Concepts

  • Quick Sort - Uses partitioning
  • Quick Select - Partitioning for selection
  • Two Pointers - Core technique
  • In-Place Operations - Often combined

Array partitioning is fundamental to many algorithms. Master these patterns, and you'll efficiently reorganize arrays and solve partitioning problems in coding interviews.

← PreviousMonotonic QueueNext →Next Greater Element