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. The partitioning should be done in-place, and the order of elements within each segment does not matter. Return the modified array as the output.

Codemia · Accepted Answer

To solve the problem of partitioning the array around a pivot in O(n) time complexity, we can utilize the **two pointers technique**. This approach is effective here because we need to rearrange elements based on a specific condition (less than or greater than/equal to the pivot). The two pointers will allow us to traverse the array in a single pass, maintaining an efficient O(n) time complexity while modifying the array in-place. We will have one pointer scanning from the start of the array and another pointer to track the position of the last element that is less than the pivot. 1. Initialize a pointer `less_than_index` at the start of the array. This pointer will mark the boundary of the partition. 2. Iterate through the array with another pointer `i`. 3. For each element at index `i`: - If the element is less than the pivot, swap it with the element at `less_than_index` and increment `less_than_index`. - If the element is greater than or equal to the pivot, simply continue to the next element. 4. Continue this until `i` reaches the end of the array. 5. The array will be partitioned into two segments: elements less than the pivot followed by elements greater than or equal to the pivot, all done in a single pass. **Example:** For the array `[3, 5, 2, 8, 6, 1, 4]` and pivot `4`: - Start with `less_than_index = 0`. - Iterate: - `3 < 4`: Swap `3` with `arr[0]` (itself). Increment `less_than_index` to 1. - `5 >= 4`: Continue. - `2 < 4`: Swap `2` with `arr[1]`, increment `less_than_index` to 2. - `8 >= 4`: Continue. - `6 >= 4`: Continue. - `1 < 4`: Swap `1` with `arr[2]`, increment `less_than_index` to 3. - Final state of the array might look like `[3, 2, 1, 8, 6, 5, 4]`. Here is the Python implementation of the above approach: ```python def partition_array(arr, pivot): less_than_index = 0 for i in range(len(arr)): if arr[i] < pivot: arr[less_than_index], arr[i] = arr[i], arr[less_than_index] less_than_index += 1 return arr ``` **Usage Example:** ```python arr = [3, 5, 2, 8, 6, 1, 4] pivot = 4 print(partition_array(arr, pivot)) # Output could be [3, 2, 1, 8, 6, 5, 4] or similar, depending on the order of elements. ``` The time complexity of this algorithm is **O(n)** because we traverse the list once using a single loop. The space complexity is **O(1)** since we are doing the partitioning in-place without utilizing any additional data structures that grow with the input size. This efficiency is particularly important given that the input can be large, and maintaining linear time complexity ensures that our solution scales well. 1. **Empty Array:** If the input array is empty, return it as is. - Example: `[]` should return `[]`. 2. **All Elements Less than Pivot:** If all elements are less than the pivot, the array remains unchanged. - Example: For `[1, 2, 3]` with pivot `5`, the output is `[1, 2, 3]`. 3. **All Elements Greater than or Equal to Pivot:** If all elements are greater than or equal to the pivot, the array also remains unchanged. - Example: For `[5, 6, 7]` with pivot `4`, the output is `[5, 6, 7]`. 4. **Single Element Array:** If the array consists of a single element, it should return the array as is. - Example: `[3]` with pivot `3` returns `[3]`.

Optimize partitioning for O(n) time

Salesforce

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

Salesforce 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