Optimize partitioning for O(1) space

Question

Given an array of integers, partition the array into two subsets such that all elements in one subset are less than a specified pivot value and all elements in the other subset are greater than or equal to the pivot. The challenge is to perform this partitioning in-place while using O(1) additional space and maintaining the relative order of elements. Your solution should return the modified array as output.

Codemia · Accepted Answer

To solve the problem of partitioning the array around a pivot while maintaining the relative order of elements, we can employ the **two-pointer technique**. This technique allows us to traverse the array with two pointers, effectively separating elements based on their comparison to the pivot. The key challenge is to preserve the order of elements, which makes a simple swap approach (like in quicksort) unsuitable. Instead, we'll use a stable partitioning strategy to ensure that elements less than the pivot are moved to the front without disrupting their original sequence.

1. **Initialization**: Start with two pointers, `left` at the beginning of the array and `right` at the end. Both will help us traverse the array.

2. **Traverse the Array**: 
   - Loop through the array using the `right` pointer. For each element, if it is less than the pivot, move it to the `left` pointer's position and increment `left`. This way, all elements less than the pivot are gathered at the front of the array. 
   - If an element is greater than or equal to the pivot, simply move the `right` pointer leftwards.

3. **Maintaining Order**: Since we are always moving elements less than the pivot to the front and leaving the rest in place, we maintain the original order of both groups.

4. **Completion**: Once the `right` pointer has traversed the entire array, the `left` pointer will indicate the boundary where elements are less than the pivot, thus completing the partitioning.

**Example**: Given `arr = [3, 1, 4, 2, 5]` and `pivot = 3`, the algorithm will rearrange the array to `[1, 2, 3, 4, 5]`.

Here's the Python implementation of the described approach:

```python
def partition_array(arr, pivot):
    left = 0  # Pointer for elements less than pivot
    right = 0  # Pointer to traverse the array

while right < len(arr):
        if arr[right] < pivot:
            arr[left], arr[right] = arr[right], arr[left]  # Swap to maintain order
            left += 1  # Move left pointer right
        right += 1  # Always move right pointer

return arr

# Example usage:
result = partition_array([3, 1, 4, 2, 5], 3)
print(result)  # Output: [1, 2, 3, 4, 5]
```

The time complexity of this approach is **O(n)**, where `n` is the number of elements in the array. This is because we make a single pass through the array with the `right` pointer. The space complexity is **O(1)** since we are modifying the array in place and only using a couple of additional pointers (`left` and `right`). This meets the requirement of using O(1) additional space.

1. **All Elements Less than Pivot**: For an array like `[1, 2, 2]` with a pivot of `3`, the output should be unchanged: `[1, 2, 2]`. 
2. **All Elements Greater than or Equal to Pivot**: For an array like `[4, 5, 6]` with a pivot of `3`, the output should also be unchanged: `[4, 5, 6]`. 
3. **Empty Array**: If the input is an empty array `[]`, the output should still be `[]`. 
4. **Single Element**: For an array with one element like `[2]` and a pivot of `3`, the output should be `[2]`, preserving the single element.

Optimize partitioning for O(1) space

Palo Alto Networks

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

Palo Alto Networks 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