mediumSortingPattern: Dutch National Flag
Three Way Array Partition Solution
Problem Statement
Given an array of integers `arr`, partition it in-place such that all elements less than a given pivot `lowerBound` come before all elements between `lowerBound` and `upperBound` (inclusive), and all elements greater than `upperBound` come after them. The relative order of elements within each partition does not need to be preserved.
Examples
Example 1:
Input:arr = [9, 12, 3, 15, 7, 10, 18, 5, 14], lowerBound = 8, upperBound = 15
Output:undefined
Explanation: Elements less than 8 are [3, 7, 5]. Elements between 8 and 15 inclusive are [9, 12, 15, 10, 14]. Elements greater than 15 are [18]. The output array contains these elements partitioned correctly. The order within partitions is not preserved.
Example 2:
Input:arr = [1, 2, 3, 4, 5], lowerBound = 2, upperBound = 4
Output:undefined
Explanation: Elements less than 2 is [1]. Elements between 2 and 4 inclusive are [2, 3, 4]. Elements greater than 4 is [5]. The array is already partitioned correctly.
Example 3:
Input:arr = [5, 5, 5, 5], lowerBound = 4, upperBound = 6
Output:undefined
Explanation: All elements are within the bounds, so the array remains unchanged.
Constraints
- 1 <= arr.length <= 10^5
- 0 <= arr[i] <= 10^9
- 0 <= lowerBound <= upperBound <= 10^9
Time: O(n) Space: O(1)
The optimal approach uses the Dutch National Flag algorithm. It iterates through the array using three pointers: `low`, `mid`, and `high`. Elements less than `lowerBound` are moved to the `low` end, elements greater than `upperBound` are moved to the `high` end, and elements within the bounds remain in the middle. This is done in-place with a single pass.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def three_way_partition(arr: list[int], lower_bound: int, upper_bound: int) -> None:
"""
Do not return anything, modify arr in-place instead.
"""
low = 0
mid = 0
high = len(arr) - 1
while mid <= high:
if arr[mid] < lower_bound:
arr[low], arr[mid] = arr[mid], arr[low]
low += 1
mid += 1
elif arr[mid] > upper_bound:
arr[mid], arr[high] = arr[high], arr[mid]
high -= 1
else:
mid += 1