# LC 31. Next Permutation

### [Problem link](https://leetcode.com/problems/next-permutation/)

###### tags: `leedcode` `python` `c++` `medium` `Two Pointer`

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

- For example, for <code>arr = [1,2,3]</code>, the following are all the permutations of <code>arr</code>: <code>[1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]</code>.

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 <code>arr = [1,2,3]</code> is <code>[1,3,2]</code>.
- Similarly, the next permutation of <code>arr = [2,3,1]</code> is <code>[3,1,2]</code>.
- While the next permutation of <code>arr = [3,2,1]</code> is <code>[1,2,3]</code> because <code>[3,2,1]</code> does not have a lexicographical larger rearrangement.

Given an array of integers <code>nums</code>, find the next permutation of <code>nums</code>.

The replacement must be **<a href="http://en.wikipedia.org/wiki/In-place_algorithm" target="_blank">in place</a>** and use only constant extra memory.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

- <code>1 <= nums.length <= 100</code>
- <code>0 <= nums[i] <= 100</code>

## Solution 1 - Two Pointer
#### Python

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)

        def reverse(left, right):
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        for i in range(n - 2, -1, -1):
            if nums[i] >= nums[i + 1]:
                continue
            for j in range(n - 1, i, -1):
                if nums[j] <= nums[i]:
                    continue
                nums[i], nums[j] = nums[j], nums[i]
                reverse(i + 1, n - 1)
                return

        reverse(0, n - 1)

#### C++

class Solution {
public:
    vector<int>::reverse_iterator is_sort_until(vector<int>::reverse_iterator begin, vector<int>::reverse_iterator end) {
        if (begin == end) {
            return begin;
        }
        auto it = begin + 1;
        while (it != end && *it >= *begin) {
            it++;
            begin++;
        }
        return it;
    }

    void nextPermutation(vector<int>& nums) {
        auto it = is_sort_until(nums.rbegin(), nums.rend());
        // auto it = is_sorted_until(nums.rbegin(), nums.rend());
        
        if (it == nums.rend()) {
            reverse(nums.begin(), nums.end());
        } else {
            auto it2 = upper_bound(nums.rbegin(), it, *it);
            swap(*it, *it2);
            reverse(nums.rbegin(), it);
        }
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(1) |

## Note
sol1:
1. 從後往前找第一個decreasing element的idx, idx1
2. 從後往前找第一個大於decreasing element的element's idx, idx_2
3. 交換nums[idx1], nums[idx2]
4. 反轉nums[idx1 + 1:]