Leetcode 60: Permutation Sequence

The simple, obvious, inefficient way to solve this is to call next_permutation() k times. But that results in O(n!), which is slow. It is also possible in O(n) time, which relies on cutting through the problem space for each digit. So when k=4, on an n=3 problem, we know that the first digit will appear twice as 1, twice as 2 and twice as 3. We know that k=4 lands on the middle third of the problem space, so the first digit must be 2. We can progress like this through the rest of the digits. It is quite confusing to code. I found I had to plan it all out with formulas before (see whiteboard).

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published.