Optimize partitioning for O(n) time

Question

Given an array of integers, implement an algorithm to partition the array into two segments such that all elements less than a specified pivot are on one side and all elements greater than or equal to the pivot are on the other side, achieving this in O(n) time complexity. Your solution should modify the array in place and return the indices of the two partitions.

Codemia · Accepted Answer

To solve the partitioning problem, we can leverage the **two pointers** technique. This technique is particularly useful here because we need to rearrange the elements of the array in a single pass without using extra space. By maintaining two pointers, we can effectively categorize elements into those less than the pivot and those greater than or equal to the pivot as we traverse the array. The left pointer will track the position where the next smaller element should be placed, and the right pointer will iterate through the array. 1. Initialize two pointers: `left` starting at the beginning of the array and `right` starting at the end. 2. Traverse the array with the `right` pointer: - If the current element (arr[right]) is less than the pivot, swap it with arr[left] and increment `left`. - If the current element is greater than or equal to the pivot, just decrement `right`. 3. Continue this until the `right` pointer crosses the `left` pointer. 4. The indices `left` and `right` will give us the bounds of the partition. **Example:** Given the array [3, 5, 2, 8, 6] and pivot = 5: - Initialize: left = 0, right = 4. - Iterating: - right = 4 (arr[4] = 6 >= 5) -> decrement right. - right = 3 (arr[3] = 8 >= 5) -> decrement right. - right = 2 (arr[2] = 2 < 5) -> swap arr[0] and arr[2] -> Array becomes [2, 5, 3, 8, 6], increment left. - Continue this until left <= right. ```python def partition_array(arr, pivot): left, right = 0, len(arr) - 1 while left <= right: while left <= right and arr[left] < pivot: left += 1 while left <= right and arr[right] >= pivot: right -= 1 if left <= right: arr[left], arr[right] = arr[right], arr[left] left += 1 right -= 1 return left, right ``` The time complexity of this solution is O(n) since we are making a single pass through the array with the right pointer. The space complexity is O(1) because we are not using any additional data structures that scale with input size. This is optimal given the constraint to modify the array in place. 1. **Empty Array**: The function should return (0, -1) since there are no elements to partition. 2. **All Elements Less Than Pivot**: For an array like [1, 2, 3] with pivot = 4, it should return indices that encompass the entire array, e.g., (3, -1). 3. **All Elements Greater Than or Equal to Pivot**: For an array like [5, 6, 7] with pivot = 4, it should also return (0, 2). 4. **Array with Duplicate Values**: The algorithm should handle duplicates correctly, ensuring they are partitioned properly based on the pivot.

Optimize partitioning for O(n) time

Cloudflare

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Cloudflare Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string