Partition Array According To Given Pivot - Leetcode Solution

Problem Statement:

Given an array of integers nums and an integer pivot, partition the array into two subarrays such that:

• All elements less than pivot are in the first subarray.
• All elements greater than or equal to pivot are in the second subarray.

Return the partitioned array.

It is guaranteed that the length of nums will be in the range [1, 10^5]. 0 <= nums[i] <= 10^6 0 <= pivot <= 10^6

Solution:

The problem statement says that we need to partition the given array into two parts depending upon the pivot value that is given. From the problem statement, we know that all the elements less than the pivot should be in the first subarray and all the elements greater than or equal to the pivot should be in the second subarray.

One way to solve this problem is to maintain two pointers: a low pointer and a high pointer. We can initialize the low pointer to the first index of the array and the high pointer to the last index of the array. We start by traversing the array from left to right until we reach an element that is greater than or equal to pivot. We then traverse the array from right to left until we reach an element that is less than the pivot.

If the left pointer is less than the right pointer, we swap the left and right elements. We repeat this process until the left pointer is greater than or equal to the right pointer. This will partition the array into two parts: the left part with elements less than the pivot and the right part with elements greater than or equal to the pivot.

Algorithm:

1. Initialize the low pointer to the first index of the array.
2. Initialize the high pointer to the last index of the array.
3. Traverse the array from left to right until an element greater than or equal to the pivot is found.
4. Traverse the array from right to left until an element less than the pivot is found.
5. Swap the left and right elements if the left pointer is less than the right pointer.
6. Repeat steps 3-5 until the left pointer is greater than or equal to the right pointer.
7. Return the partitioned array.

Code:

class Solution {
    public int[] partitionArray(int[] nums, int pivot) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            while (nums[low] < pivot) {
                low++;
            }
            while (nums[high] >= pivot) {
                high--;
            }
            if (low <= high) {
                int temp = nums[low];
                nums[low] = nums[high];
                nums[high] = temp;
                low++;
                high--;
            }
        }
        return nums;
    }
}

Time Complexity: O(n) as we are doing a linear scan of the array.

Space Complexity: O(1) since we are not using any extra space, just two pointers and a temp variable.

1