Optimize partitioning for O(1) space

Question

Given an array of integers, optimize the partitioning of the array 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, using O(1) additional space. The function should return the rearranged array in-place while maintaining the order of elements within each partition.

Codemia · Accepted Answer

The problem requires us to partition an array based on a pivot such that all elements less than the pivot are on one side and all elements greater than or equal to the pivot are on the other side. The key requirement is to achieve this in-place using O(1) additional space. The two-pointer technique is suitable here because it allows us to traverse the array with a minimal amount of extra space while rearranging elements. One pointer can traverse the array to find elements that should be on the 'less than' side, while the other pointer can keep track of the current position to swap elements as needed.

1. Initialize two pointers: `left` at the start of the array and `right` at the end of the array.
2. Iterate through the array with the `left` pointer moving right. For each element:
   - If it is less than the pivot, swap it with the element at the `right` pointer and decrement `right`.
   - If it is greater than or equal to the pivot, simply move the `left` pointer one step to the right.
3. Continue this process until the `left` pointer meets or exceeds the `right` pointer.
4. The elements will be partitioned correctly and can be returned as the final array.

**Example:** For the input array `[3, 1, 4, 2, 5]` with pivot `3`, the process would look like:
- Start: `left = 0`, `right = 4` with array unchanged.
- Move `left` to `1`, swap `1` (less than `3`) with `5`, array becomes `[3, 5, 4, 2, 1]`.
- Move `left` to `2`, swap `4` (not less than `3`), just move `left` again.
- Move `left` to `3`, swap `2` (less than `3`) with `4`, array becomes `[3, 5, 2, 4, 1]`.
- Continue until the partitioning is done.

Here is the Python code implementing the above approach:

```python
def partition_array(arr, pivot):
    left = 0
    right = len(arr) - 1

while left <= right:
        if arr[left] < pivot:
            left += 1
        else:
            arr[left], arr[right] = arr[right], arr[left]
            right -= 1

return arr
```

This function modifies the input array in place and returns the rearranged array.

The time complexity of this solution is O(n), where n is the number of elements in the array. This is because we are making a single pass through the array with the two pointers. The space complexity is O(1) since we are only using a constant amount of extra space for the pointers.

1. **Empty Array:** If the input array is empty, the function should return an empty array without errors.
2. **All Elements Less than Pivot:** If all elements are less than the pivot, the array should remain unchanged.
3. **All Elements Greater than or Equal to Pivot:** If all elements are greater than or equal to the pivot, the array should also remain unchanged.
4. **Pivot Not Present in Array:** If the pivot is not present, the array should still be partitioned correctly based on the elements relative to the pivot.
5. **Single Element Array:** The function should return the same single-element array as there are no elements to partition.

Optimize partitioning for O(1) space

Jump Trading

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

Jump Trading 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