Permutation Sequence

So a few days ago I attempted to do Leetcode 60, permutation sequence. The problem seems simple enough, it goes something like the following. Given an integer n and an integer k, return the value of the kth permutation in the sequence of sorted permutations from [1…n]. So for example, if n and k are both equal to 3, then the sorted permutations (in ascending order) would be “123, 132, 213, 231, 312, 321”, and “213” would be returned.

So, for my brute force approach, I created a new array with numbers from [1…n], and then I created another method within the solution class to create all the subsets of that array, and then I returned the (k-1) element in that array as a string.

But since this is leetcode and I wrote my solution in python, a Time Limit Exceeded error was returned. I then tried to think of a few other ways to solve this problem that could be faster, but couldn’t think of one. So I went on youtube and looked around at solution videos.

Now, I seriously hope that I never get asked this question in an interview, because the method that I saw used in the two videos I watched seemed over-the-top complicated. One of the people giving the tutorial even said it took him more than just a few hours to come up with a solution for the problem, and that it turned out to be so idiosyncratic that it can’t even really be applied to any other problem.

I have to admit, even after studying the solution they came up with and writing it myself, I still don’t fully remember it just a few days later. Usually, when I come up with a solution on leetcode, I go back a few weeks later to questions I feel are important and retry them, and I’m able to at least get a good understanding of the approach I need to take. But with this question, I would have to repeatedly study it to remember the approach.

That’s not to say that the provided solutions aren’t clever. They’re really, really clever. Sometimes it just seems like leetcode tries too hard to make things, well, too hard.

1 comment

1. Hi, this is a comment.
To get started with moderating, editing, and deleting comments, please visit the Comments screen in the dashboard.
Commenter avatars come from Gravatar.