DDSA Solutions

2161. Partition Array According to Given Pivot

MediumView on LeetCode
ArrayTwo PointersSorting
Time: O(n)
Space: O(n)

Problem Overview

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

Intuition

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

Algorithm

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

Common Pitfalls

  • •Maintain relative order within each group. Three-pass approach is simplest.
2161.cs
C#
// 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?

Related Problems