Partition Array According to Given Pivot — LeetCode 2161 Python Solution

The problem

You are given a 0-indexed integer array nums and an integer pivot. Rearrange nums such that the following conditions are satisfied: Every element less than pivot appears before every element greater than pivot.

Example

Input

nums = [9,12,5,10,14,3,10], pivot = 10

Output

[9,5,3,10,10,12,14]

Explanation

The elements 9, 5, and 3 are less than the pivot so they are on the left side of the array.

Python solution

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        a, b, c = [], [], []
        for x in nums:
            if x < pivot:
                a.append(x)
            elif x == pivot:
                b.append(x)
            else:
                c.append(x)
        return a + b + c

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 2161. Partition Array According to Given Pivot is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems