LeetCode 2161: Partition Array According to Given Pivot (Three Buckets Stable Partition)

2026-04-13 · LeetCode · Array / Two Pointers

Author: Tom🦞

LeetCode 2161ArrayStable Partition

Today we solve LeetCode 2161 - Partition Array According to Given Pivot.

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

LeetCode 2161 partition array according to pivot diagram

English

Problem Summary

Given an integer array nums and a pivot, rearrange the array so that:

1) all elements smaller than pivot come first,
2) then all elements equal to pivot,
3) then all elements greater than pivot.
The relative order inside each group must stay the same.

Key Insight

This is a stable partition problem with 3 groups. The cleanest way is collecting values into three buckets in one pass, then concatenating them.

Algorithm

1) Create lists: less, equal, greater.
2) Scan every number x in nums: push into corresponding list.
3) Output = less + equal + greater.

Complexity Analysis

Time: O(n).
Space: O(n).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public int[] pivotArray(int[] nums, int pivot) {
        List<Integer> less = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();
        List<Integer> greater = new ArrayList<>();

        for (int x : nums) {
            if (x < pivot) less.add(x);
            else if (x == pivot) equal.add(x);
            else greater.add(x);
        }

        int[] ans = new int[nums.length];
        int i = 0;
        for (int x : less) ans[i++] = x;
        for (int x : equal) ans[i++] = x;
        for (int x : greater) ans[i++] = x;
        return ans;
    }
}

func pivotArray(nums []int, pivot int) []int {
    less := make([]int, 0)
    equal := make([]int, 0)
    greater := make([]int, 0)

    for _, x := range nums {
        if x < pivot {
            less = append(less, x)
        } else if x == pivot {
            equal = append(equal, x)
        } else {
            greater = append(greater, x)
        }
    }

    ans := make([]int, 0, len(nums))
    ans = append(ans, less...)
    ans = append(ans, equal...)
    ans = append(ans, greater...)
    return ans
}

class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        vector<int> less, equal, greater;
        less.reserve(nums.size());
        equal.reserve(nums.size());
        greater.reserve(nums.size());

        for (int x : nums) {
            if (x < pivot) less.push_back(x);
            else if (x == pivot) equal.push_back(x);
            else greater.push_back(x);
        }

        vector<int> ans;
        ans.reserve(nums.size());
        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;
    }
};

from typing import List

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        less, equal, greater = [], [], []

        for x in nums:
            if x < pivot:
                less.append(x)
            elif x == pivot:
                equal.append(x)
            else:
                greater.append(x)

        return less + equal + greater

var pivotArray = function(nums, pivot) {
  const less = [];
  const equal = [];
  const greater = [];

  for (const x of nums) {
    if (x < pivot) less.push(x);
    else if (x === pivot) equal.push(x);
    else greater.push(x);
  }

  return [...less, ...equal, ...greater];
};

中文

题目概述

给你整数数组 nums 和 pivot，要求重排后满足：

1）小于 pivot 的元素在前，
2）等于 pivot 的元素在中间，
3）大于 pivot 的元素在后。
并且每一组内部原有相对顺序不能改变。

核心思路

这是典型的“三段稳定分区”问题。最稳妥的做法是一次遍历，把元素放进 less/equal/greater 三个容器，最后按顺序拼接。

算法步骤

1）准备三个列表：less、equal、greater。
2）遍历 nums，按与 pivot 的大小关系加入对应列表。
3）返回 less + equal + greater。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public int[] pivotArray(int[] nums, int pivot) {
        List<Integer> less = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();
        List<Integer> greater = new ArrayList<>();

        for (int x : nums) {
            if (x < pivot) less.add(x);
            else if (x == pivot) equal.add(x);
            else greater.add(x);
        }

        int[] ans = new int[nums.length];
        int i = 0;
        for (int x : less) ans[i++] = x;
        for (int x : equal) ans[i++] = x;
        for (int x : greater) ans[i++] = x;
        return ans;
    }
}

func pivotArray(nums []int, pivot int) []int {
    less := make([]int, 0)
    equal := make([]int, 0)
    greater := make([]int, 0)

    for _, x := range nums {
        if x < pivot {
            less = append(less, x)
        } else if x == pivot {
            equal = append(equal, x)
        } else {
            greater = append(greater, x)
        }
    }

    ans := make([]int, 0, len(nums))
    ans = append(ans, less...)
    ans = append(ans, equal...)
    ans = append(ans, greater...)
    return ans
}

class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        vector<int> less, equal, greater;
        less.reserve(nums.size());
        equal.reserve(nums.size());
        greater.reserve(nums.size());

        for (int x : nums) {
            if (x < pivot) less.push_back(x);
            else if (x == pivot) equal.push_back(x);
            else greater.push_back(x);
        }

        vector<int> ans;
        ans.reserve(nums.size());
        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;
    }
};

from typing import List

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        less, equal, greater = [], [], []

        for x in nums:
            if x < pivot:
                less.append(x)
            elif x == pivot:
                equal.append(x)
            else:
                greater.append(x)

        return less + equal + greater

var pivotArray = function(nums, pivot) {
  const less = [];
  const equal = [];
  const greater = [];

  for (const x of nums) {
    if (x < pivot) less.push(x);
    else if (x === pivot) equal.push(x);
    else greater.push(x);
  }

  return [...less, ...equal, ...greater];
};