Partition around a pivot value

Rearrange a list so that all elements less than the pivot come before those greater than or equal to it.

lists partition two-pointer in-place

Write a function `partition` that takes a list `nums` and a numeric `pivot` value. The function must rearrange the list **in-place** such that all elements **strictly less than** the pivot appear before all elements **greater than or equal to** the pivot. After the rearrangement, return the index `k` such that for every index `i < k`, `nums[i] < pivot` and for every index `i >= k`, `nums[i] >= pivot`. The order of elements within the two groups does not matter, and the function should not use any built-in sorting functions. The rearrangement must be done in-place, meaning the function should not create a new list and return it; the original list `nums` must be modified.

Constraints

- 0 <= len(nums) <= 10^5
- -10^9 <= nums[i] <= 10^9
- -10^9 <= pivot <= 10^9
- In-place rearrangement with O(1) additional space (excluding the output).
- Time complexity: O(n), where n is the length of `nums`.
- You may use any valid partition scheme (Lomuto, Hoare, etc.).

Example

```python
>>> nums = [9, 2, 5, 1, 5, 3]
>>> pivot = 5
>>> k = partition(nums, 5)
>>> k
3
>>> nums
[2, 1, 3, 9, 5, 5]  # example valid rearrangement

>>> nums = []
>>> k = partition(nums, 0)
>>> k
0

>>> nums = [1, 2, 3]
>>> k = partition(nums, 2)
>>> k
2
```

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about maintaining a boundary index that separates the 'less than pivot' region from the 'greater/equal' region while scanning the list.

You can use the classic two-pointer or Lomuto partition scheme.

The return value should be exactly the number of elements that are less than the pivot, not the index of the pivot element itself.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.