> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Next Permutation Python Solution with Tests

> Tested Python solution for LeetCode 31 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 31, Medium. Topics: Array, Two Pointers. [View on LeetCode](https://leetcode.com/problems/next-permutation/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 31   # by problem number
lcpy gen -s next_permutation   # by problem name
```

## Problem

A **permutation** of an array of integers is an arrangement of its members into a sequence or linear order.

* For example, for `arr = [1,2,3]`, the following are all the permutations of `arr`: `[1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]`.

The **next permutation** of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the **next permutation** of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

* For example, the next permutation of `arr = [1,2,3]` is `[1,3,2]`.
* Similarly, the next permutation of `arr = [2,3,1]` is `[3,1,2]`.
* While the next permutation of `arr = [3,2,1]` is `[1,2,3]` because `[3,2,1]` does not have a lexicographical larger rearrangement.

Given an array of integers `nums`, find the next permutation of `nums`.

The replacement must be **in place** and use only constant extra memory.

### Examples

```
Input: nums = [1,2,3]
Output: [1,3,2]
```

```
Input: nums = [3,2,1]
Output: [1,2,3]
```

```
Input: nums = [1,1,5]
Output: [1,5,1]
```

### Constraints

* `1 <= nums.length <= 100`
* `0 <= nums[i] <= 100`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/next_permutation/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/next_permutation/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n)
    # Space: O(1)
    def next_permutation(self, nums: list[int]) -> None:
        # Find pivot (rightmost ascending pair)
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        if i >= 0:
            # Find successor (rightmost element > pivot)
            j = len(nums) - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

        # Reverse suffix
        left, right = i + 1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
```

## Complexity

| Time | Space |
| ---- | ----- |
| O(n) | O(1)  |

## Tags

[Grind](/catalog/grind), [NeetCode All](/catalog/neetcode).