[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.
- 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.
Take a example, which is decreasing order, there is no next permutation, it is already stable and cannot get larger.
Like , 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, , the 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, , after swap: .
However, it’s not over yet!
The magnitude of the increase can be made smaller, the 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 , which is what is required.
// Two Pointers time: O(n) space: O(1)
- Time Complexity:
- Space Complexity:
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. 😉😃💗