Partition Array According to Given Pivot

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& arr, int key) {
        vector<int> result(arr.size());
        int lowIndex = 0;
        int highIndex = arr.size() - 1;
        for (int low = 0, high = arr.size() - 1; low < arr.size(); low++, high--) {
            if (arr[low] < key) {
                result[lowIndex] = arr[low];
                lowIndex++;
            }
            if (arr[high] > key) {
                result[highIndex] = arr[high];
                highIndex--;
            }
        }
        while (lowIndex <= highIndex) {
            result[lowIndex] = key;
            lowIndex++;
        }
        return result;
    }
};

The described C++ solution focuses on rearranging an array based on a given pivot, key. The function rearrangeArray takes in two parameters: a vector of integers arr and the integer key. The goal is to reorder the elements of arr such that all elements less than key are on the left, all elements greater than key are on the right, and all instances of key (if any) fill the middle positions of the resulting vector.

Here's a breakdown of the approach:

• result vector is initialized with the same size as arr to store the rearranged elements.
• Two indices, lowIndex and highIndex, are used for placing smaller elements from the start and larger elements from the end of the result vector, respectively.
• Iterate over the array with two pointers, low starting from the beginning and high from the end. During the iteration:
  • If arr[low] is less than key, place it at the result[lowIndex] and increment lowIndex.
  • Conversely, if arr[high] is greater than key, place it at result[highIndex] and decrement highIndex.
• After processing all elements in arr, fill the gap between lowIndex and highIndex in result with the pivot value key.

This method efficiently partitions the array into three segments using a single traversal and without extra space for another array, adhering to in-place principles. Ensure to handle edge cases, such as arrays containing all elements equal to key, very small arrays, or arrays with no elements equal to key.

class Solution {
    
    public int[] rearrangeArray(int[] elements, int pivotValue) {
        int[] result = new int[elements.length];
        int lessIndex = 0;
        int greaterIndex = elements.length - 1;
        for (int i = 0, j = elements.length - 1; i < elements.length; i++, j--) {
            if (elements[i] < pivotValue) {
                result[lessIndex] = elements[i];
                lessIndex++;
            }
            if (elements[j] > pivotValue) {
                result[greaterIndex] = elements[j];
                greaterIndex--;
            }
        }
        while (lessIndex <= greaterIndex) {
            result[lessIndex] = pivotValue;
            lessIndex++;
        }
        return result;
    }
}

This Java solution tackles the problem of reorganizing an array relative to a given pivot value. The rearrangeArray method in the Solution class modifies the order of elements in the input array elements based on their comparison with pivotValue. The resulting array places all elements less than the pivot before those greater than the pivot, with occurrences of the pivot value in between.

Here is an outline of how the method works:

• Initialize result, an array of the same length as elements to store the rearranged values.
• Use two index pointers, lessIndex and greaterIndex. lessIndex starts from the beginning of the array, while greaterIndex starts from the end.
• Iterate through the elements array using two variables in a for loop, i incrementing from the start and j decrementing from the end. This allows simultaneous placement of smaller and larger elements in their respective positions in the result.
• If an element indexed by i is less than the pivot, it's placed at the current lessIndex position in result, and lessIndex is incremented.
• Similarly, if an element indexed by j is greater than the pivot, it's placed at the current greaterIndex position in result, and greaterIndex is decremented.
• After the loop, fill up any indices between lessIndex and greaterIndex with the pivotValue.

This method ensures a traversal efficiency of O(n), where n is the number of elements in the array, and performs the separation in one pass with additional filling of pivot values in a contiguous mid-section. This arrangement guarantees the elements relative to the pivot are placed as desired without the need for additional sorting steps.

class Solution:
    def rearrangeArray(self, array, key):
        output = [0] * len(array)
        lower_index = 0
        upper_index = len(array) - 1
    
        for forward, backward in zip(range(len(array)), range(len(array) - 1, -1, -1)):
            if array[forward] < key:
                output[lower_index] = array[forward]
                lower_index += 1
            if array[backward] > key:
                output[upper_index] = array[backward]
                upper_index -= 1
    
        while lower_index <= upper_index:
            output[lower_index] = key
            lower_index += 1
    
        return output

This summary explains how the provided Python solution can rearrange an array with respect to a given pivot (key) so that all elements less than the key are positioned before it, and all elements greater are positioned after it.

• The solution employs a class named Solution with a method rearrangeArray taking two parameters - array which is the list of integers to rearrange, and key, the pivot element.
• A new list output is initialized with zeros to hold the rearranged elements. Its size matches that of array.
• Using two pointers, lower_index initialized at the start of the list and upper_index initialized at the end, the method iterates through the list:
  • Traverse from both ends of the array simultaneously using a for loop. forward moves from the beginning toward the middle, while backward moves from the end backward.
  • If the element at the forward index is less than key, it's placed at the current lower_index in the output, and lower_index is incremented.
  • Similarly, if the element at the backward index is greater than key, it's placed at the current upper_index in the output, and upper_index is decremented.
• After completing the initial passes, fill any remaining positions (where lower_index has not yet met upper_index) with the key. This accounts for elements that are exactly equal to the pivot.
• The method completes by returning the output array now partitioned according to the specified key.

This approach ensures that the array is rearranged in a single pass with respect to the given key, efficiently partitioning the values as required.