Partition Array According to Given Pivot

Leetcode Problem:

• Partition Array According to Given Pivot

Summary

• Given an array of integers and a pivot value, rearrange the array such that all elements less than the pivot appear before all elements greater than the pivot, and elements equal to the pivot appear in between.

Approach

• Separate the array into three lists: less than pivot, equal to pivot, and greater than pivot
• Then, concatenate these lists to form the rearranged array.

Complexity

• O(n), where n is the number of elements in the array
• This is because each element in the array is visited once.

Explanation

• This solution uses three lists to separate the array into three categories based on the pivot value
• Then, it concatenates these lists to form the rearranged array
• This approach ensures that all elements less than the pivot appear before all elements greater than the pivot, and elements equal to the pivot appear in between
• The time complexity is O(n) because each element in the array is visited once.

Solution Code:

class Solution {
public:
    vector pivotArray(vector& nums, int pivot) {
        vector less;
        vector equal;
        vector greater;
        for(int i = 0 ; i < nums.size(); i++){
            if(nums[i] < pivot){
                less.push_back(nums[i]);
            } else if(nums[i] > pivot){
                greater.push_back(nums[i]);
            } else{
                equal.push_back(nums[i]);
            }
        }
        vector ans;
        ans.insert(ans.end(), less.begin(), less.end());
        ans.insert(ans.end(), equal.begin(), equal.end());
        ans.insert(ans.end(), greater.begin(), greater.end());
        return ans;
    }
};