mediumArraysPattern: Dutch National Flag
Three-Way Pivot Partitioning Solution
Problem Statement
Given an array of integers `nums` and an integer `pivot`, rearrange the elements of `nums` in-place such that all elements less than `pivot` appear first, followed by all elements equal to `pivot`, and finally all elements greater than `pivot` appear last. You must solve this problem in-place with O(1) auxiliary space and in O(N) time complexity. The relative order of the partitioned elements does not need to be preserved.
Examples
Example 1:
Input:nums = [9, 12, 3, 5, 14, 5, 10, 5], pivot = 5
Output:undefined
Explanation: The elements strictly less than 5 are [3]. The elements equal to 5 are [5, 5, 5]. The elements strictly greater than 5 are [9, 12, 14, 10]. One valid partition sequence is [3, 5, 5, 5, 14, 12, 10, 9].
Example 2:
Input:nums = [4, 8, 4, 2, 7, 1], pivot = 4
Output:undefined
Explanation: The elements strictly less than 4 are [2, 1]. The elements equal to 4 are [4, 4]. The elements strictly greater than 4 are [8, 7]. A valid partitioned array is [2, 1, 4, 4, 8, 7].
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- -10^9 <= pivot <= 10^9
Time: O(N) Space: O(1)
We use Dijkstra's Dutch National Flag algorithm with three pointers: low, mid, and high. The low pointer tracks the boundary of elements less than the pivot, mid scans the current element, and high tracks the boundary of elements greater than the pivot. By swapping elements relative to these boundaries in a single pass, we achieve O(N) time complexity and O(1) auxiliary space.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from typing import List
def three_way_pivot_partitioning(nums: List[int], pivot: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] < pivot:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == pivot:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1