31. Next Permutation

tags

trick

source

leetcode

Solution

• scan from end, find first element e1 smaller than later one

• scan from e1 to end, find the smallest element e2 largger than e1

• swap e1 and e2

• reverse elements behind e1

  https://leetcode.com/problems/next-permutation/solution/

Complexity

• time: O(n), worst case, scan two times of the array
• space: O(1)