[LeetCode] 2161. Partition Array According to Given Pivot

Problem

https://leetcode.com/problems/partition-array-according-to-given-pivot/description/

Leetcode - Partition Array According to Given Pivot

Type - array, two pointers

Difficulty - Medium

Approach & Solution

data structures & variables:

• l: stores numbers that less than pivot.

• e: stores numbers that equals to pivot.

• g: stores numbers that greater than pivot.

Iterating through nums:

• if nums[i] is less than pivot, append nums[i] in array l.

• else if nums[i] is equals to pivot, append nums[i] in array e.

• else, append nums[i] in array g.

Append e and g sequentially to the back of the array l.

Return l.

Complexity

Time Complexity: O(n) - l, e, g are 1-D arrays each.

Space Complexity: O(n) - elements of l, e, g don’t exceed the number of elements of nums.

Code (C++ | Go)

class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        vector<int> l, e, g;

        for(const auto &elem : nums) {
            if(elem < pivot) l.emplace_back(elem);
            else if(elem == pivot) e.emplace_back(elem);
            else g.emplace_back(elem);
        }

        l.insert(l.end(), e.begin(), e.end());
        l.insert(l.end(), g.begin(), g.end());
        return l;
    }
};

func pivotArray(nums []int, pivot int) []int {
    l := make([]int, 0)
    e := make([]int, 0)
    g := make([]int, 0)

    for _, num := range nums {
        if num < pivot {
            l = append(l, num)
        } else if num == pivot {
            e = append(e, num)
        } else {
            g = append(g, num)
        }
    }

    l = append(l, e...)
    l = append(l, g...)

    return l
}