⚡Flashcard Drill➔
NeetCode #198LC-2161MediumTwo Pointers
← Back to All Problems

#198 · #2161 · Partition Array According to Given Pivot(根据给定数字划分数组)

📌 Problem Statement & Constraints

Given an integer array nums and an integer pivot, rearrange nums so that elements less than pivot come first, then elements equal to pivot, then elements greater than pivot, preserving the relative order within each group. Constraints: 1 <= nums.length <= 10^5, -10^5 <= nums[i], pivot <= 10^5.

💡 Core Algorithmic Approaches

  1. Because the relative order within each group must be preserved, a stable three-way partition is required.
  2. The simplest approach is three separate lists, appended in a single pass, then concatenated.
  3. This is stable by construction and O(n) time.
  4. An in-place Dutch-national-flag partition would be O(1) space but is not stable, so it does not satisfy the requirement here.

💻 Benchmark Python3 Implementation

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass to partition plus O(n) to concatenate.
💾 Space Complexity
O(n) for the three lists. Stability requires the extra space, so this is the intended trade-off.

⚠️ Interview Pitfalls & Follow-ups

  • Using an in-place Dutch-national-flag partition: it is O(1) space but unstable, so the relative order requirement would be violated.
  • Sorting with a comparator: O(n log n) and unnecessary, since only three groups exist.
  • Using <= for the first branch: elements equal to the pivot must go in the middle group, not the first.
  • Assuming the pivot must be present in nums: it need not be; the equal list is then simply empty.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems