2161. Partition Array According to Given Pivot

MediumView on LeetCode

Array Two Pointers Sorting

Time: O(n)

Space: O(n)

Intuition

Divide array into elements below pivot, equal to pivot, and above pivot, maintaining relative order.

Algorithm

1Three passes: collect elements < pivot, then == pivot, then > pivot.
2Concatenate.

Common Pitfalls

•Maintain relative order within each group. Three-pass approach is simplest.

2161.cs

// Approach: Three-pass stable partition: less-than, equal, greater-than pivot.
// Time: O(n) Space: O(n)

public class Solution
{
    public int[] PivotArray(int[] nums, int pivot)
    {
        int[] ans = new int[nums.Length];
        int i = 0; // ans' index

        foreach (int num in nums)
        {
            if (num < pivot)
                ans[i++] = num;
        }

        foreach (int num in nums)
        {
            if (num == pivot)
                ans[i++] = num;
        }

        foreach (int num in nums)
        {
            if (num > pivot)
                ans[i++] = num;
        }

        return ans;
    }
}

Was this solution helpful?