# [LeetCode][31. Next Permutation] Two Pointers Solution with Detailed Explanation

*By Long Luo*

This article is the solution Two Pointers Solution with Detailed Explanation of Problem 31. Next Permutation.

# Intuition

- How to make a number
**larger**?

Pick a **larger** number from the **lower** digit and swap it with the **higher** digit smaller number.

- How to find the permutation which is
**just larger**than the given number?

The increase should be as small as possible.

# Two Pointers

Take a example, \([3,2,1]\) which is decreasing order, there is no next permutation, it is already stable and cannot get larger.

Like \([1,5,2,4,3,2]\), how can it be just larger than the given number?

- Scanning from right to left, find the
**first**number which is smaller than the right digit, and swap it to the lower digit;- For example, \(1 5 (2) 4 3 2\), the \(2\) in the middle is the found one.

- Scanning from right to left, searching for the first number which is larger than it, and
**swap**them.- For example, \(1 5 (2) 4 (3) 2\), after swap: \(1 5 (3) 4 (2) 2\).

However, it’s not over yet!

The magnitude of the increase can be made smaller, the \(3rd\) digit from right has become slightly larger, and the last three can be made smaller.

The last three digits are definitely **decreasing**, and they are flipped to become \([1,5,3,2,2,4]\), which is what is required.

1 | // Two Pointers time: O(n) space: O(1) |

## Analysis

**Time Complexity**: \(O(n)\)**Space Complexity**: \(O(1)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗