Optimize partitioning for in-place

Question

Given an array of integers, implement an in-place algorithm to optimize the partitioning of the array such that all elements less than a specified pivot are moved to the left and all elements greater than or equal to the pivot are moved to the right. The function should return the modified array, and the partitioning should be done with O(1) additional space.

Codemia · Accepted Answer

The goal is to partition the array such that all elements less than a specified pivot are on the left side and all elements greater than or equal to the pivot are on the right side. This problem can be efficiently solved using the **two-pointer technique**. This method is suitable here because we can traverse the array while maintaining two pointers: one for tracking the position of the last element smaller than the pivot and another for iterating through the array. The two-pointer approach allows us to achieve the partitioning in a single pass, optimizing both time and space.

1. Initialize two pointers: `low` starting at the beginning of the array and `i` also starting at the beginning of the array to iterate through the array.  
2. Loop through the array with `i` until it reaches the end.  
   - If the current element `array[i]` is less than the pivot, swap `array[i]` with `array[low]` and increment both `low` and `i`.  
   - If `array[i]` is greater than or equal to the pivot, just increment `i`.  
3. Continue this process until `i` reaches the end of the array.  
4. The `low` pointer will indicate the partition point where all elements to the left are less than the pivot and all elements to the right are greater than or equal to the pivot.  
5. Return the modified array.  
**Example:** For `array = [3, 5, 2, 1, 4]` and `pivot = 3`, the array after partitioning will be `[2, 1, 3, 5, 4]`.

```python
def partition_array(array, pivot):
    low = 0
    i = 0
    while i < len(array):
        if array[i] < pivot:
            array[low], array[i] = array[i], array[low]  # Swap elements
            low += 1
        i += 1
    return array

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

The time complexity of this algorithm is **O(n)**, where `n` is the number of elements in the array. This is because we traverse the array once with the pointer `i`. The space complexity is **O(1)** since we are only using a fixed amount of extra space (for variables `low` and `i`), and the partitioning is done in place without using any additional data structures.

1. **Empty Array:** If the input array is empty, the function should return an empty array.  
2. **Single Element:** If the array has only one element, it should remain unchanged regardless of the pivot value.  
3. **All Elements Equal:** If all elements are equal to the pivot, the function should return the array unchanged.  
4. **No Elements Less Than Pivot:** If there are no elements less than the pivot, the result should still reflect the original order of the elements greater than or equal to the pivot.  
5. **No Elements Greater Than or Equal to Pivot:** Similarly, if there are no elements greater than or equal to the pivot, the result should reflect the original order of the elements less than the pivot.

Optimize partitioning for in-place

Palantir

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

Palantir 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