C++ 0060.cpp
class Solution {
public:
string getPermutation(int n, int k) {
// brute-force
string s;
for (int i = 1; i <= n; i++)
s += i + '0';
for (; k > 1; k--)
next_permutation(s.begin(), s.end());
return s;
}
};
Difficulty
and has an acceptance rate of about 54% (1+ million submissions).
Typical patterns to solve this problem:
- Math
- Recursion
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation computes the k-th lexicographic permutation of the sequence 1…n. It follows a straightforward approach: construct the initial ordered string representation of the numbers, then repeatedly invoke the standard library routine next_permutation until the desired permutation index is reached, and finally return the resulting string.
Construction of the initial sequence
The algorithm begins by creating a string that contains the digits 1 through n in ascending order. This is achieved with a simple loop that appends each integer converted to its character form.
string s;
for (int i = 1; i <= n; i++)
s += i + '0';
The expression i + '0' leverages the ASCII encoding to transform a single-digit integer into its corresponding character, avoiding the overhead of more elaborate conversion functions.
Iterative advancement to the target permutation
After the base string is prepared, the code enters a loop that decrements the target index k while repeatedly calling next_permutation. The loop condition k > 1 ensures that the initial arrangement (which corresponds to the first permutation) is returned unchanged when k equals 1.
for (; k > 1; k--)
next_permutation(s.begin(), s.end());
The use of the standard library algorithm next_permutation abstracts the permutation logic, providing a reliable and well-optimized implementation that works in-place on the character range.
Returning the result
Once the loop terminates, the string s holds the required permutation, and the function returns it directly.
return s;
Edge-case handling
When n is 1, the construction loop produces the single-character string "1". Since there is only one possible permutation, the subsequent loop never executes because k cannot be greater than 1, and the function returns "1" correctly.
If k equals 1 for any valid n, the loop body is skipped entirely, and the initially built ordered string is returned, representing the first lexicographic permutation.
The code also gracefully handles the maximum valid values of k that correspond to the total number of permutations (n!). In that scenario, the loop iterates exactly n! - 1 times, advancing through every permutation until the final one is reached. The reliance on next_permutation guarantees correct wrap-around behavior, preventing out-of-range accesses.
Performance considerations
The implementation benefits from several implicit optimizations:
-
In-place transformation:
next_permutationrearranges the characters within the existing string buffer, eliminating the need for auxiliary data structures or copying of intermediate results. -
ASCII arithmetic: Converting integers to characters via
i + '0'avoids function calls and temporary objects, reducing overhead in the initial string construction. -
Standard library efficiency: The STL algorithm is highly tuned for typical use cases, employing efficient pointer arithmetic and minimal branching to generate the next permutation.
-
Early exit for trivial cases: When
kis 1, the loop is bypassed, resulting in constant-time execution for the most common request of the first permutation.
Overall, the code leverages the strengths of the C++ standard library to keep the implementation concise while maintaining effective runtime behavior for the intended problem size.
ELI5 - Simplified Explanation
Imagine you have a row of wooden blocks, and each block has a number painted on it. You start by putting them in order from one to whatever number n is. This forms a little train of numbers.
The code works like a fun game where you rearrange those blocks to create new patterns. Every time the person playing says to go to the next step, you take the current pattern of blocks and swap them around just a little bit to make the very next version possible. You keep doing this over and over again. By the time you finish doing this k minus one times, the blocks are sitting in the exact spot that corresponds to the goal k. It is just like flipping cards in a deck until you find the specific one you are looking for.
Code Quality
Complexity Analysis
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||
| www | AlgoMonster | C++ | Python | Java | TS | |||||
| WalkCCC | C++ | Python | Java | |||||||
| leetcode.ca | C++ | Python | Rust | C# | Java | Go | TS | |||
| LeetcodeHelp | C++ | Python | Java | |||||||
| MemoryLimitExceeded | C++ | Python | ||||||||
| Progiez | C++ | Python | Java | |||||||
| github | aylei | Rust | ||||||||
| begeekmyfriend | C | |||||||||
| BigEggStudy | C# | |||||||||
| black-shadows | C++ | |||||||||
| charles-wangkai | Java | |||||||||
| chenyanzhe | C++ | |||||||||
| everthis | JS | |||||||||
| fengvyi | C++ | |||||||||
| gaosq0604 | Python | |||||||||
| Garvit244 | Python | |||||||||
| halfrost | Go | |||||||||
| haoel | C++ | |||||||||
| JoshCrozier | JS | |||||||||
| keineahnung2345 | C++ | |||||||||
| lennylxx | C++ | |||||||||
| linouk23 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| luangong | C++ | |||||||||
| MacJim | C++ | |||||||||
| qiyuangong | Python | |||||||||
| ruoru | Rust | |||||||||
| suxrobGM | C# | |||||||||
| wisdompeak | C++ | |||||||||
| XiaotaoGuo | C++ | |||||||||
| zfang399 | C++ | |||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||
| WalkCCC | C++, Python, Java | |||||||||
| leetcode.ca | C++, C#, Go, Java, Python, Rust, TypeScript | |||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||
| MemoryLimitExceeded | Python, C++ | |||||||||
| Progiez | C++, Java, Python | |||||||||
| aylei | Rust | |||||||||
| begeekmyfriend | C | |||||||||
| BigEggStudy | C# | |||||||||
| black-shadows | C++, C++ | |||||||||
| charles-wangkai | Java | |||||||||
| chenyanzhe | C++ | |||||||||
| everthis | JavaScript | |||||||||
| fengvyi | C++ | |||||||||
| gaosq0604 | Python | |||||||||
| Garvit244 | Python | |||||||||
| halfrost | Go | |||||||||
| haoel | C++ | |||||||||
| JoshCrozier | JavaScript | |||||||||
| keineahnung2345 | C++ | |||||||||
| lennylxx | C++ | |||||||||
| linouk23 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| luangong | C++ | |||||||||
| MacJim | C++ | |||||||||
| qiyuangong | Python | |||||||||
| ruoru | Rust | |||||||||
| suxrobGM | C# | |||||||||
| wisdompeak | C++ | |||||||||
| XiaotaoGuo | C++ | |||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 46: Permutations
Solved On The Same Day
- problem 125: Valid Palindrome
- problem 191: Number of 1 Bits
- problem 202: Happy Number
- problem 217: Contains Duplicate
- problem 219: Contains Duplicate II
- problem 290: Word Pattern
- problem 383: Ransom Note
- problem 392: Is Subsequence
- problem 1047: Remove All Adjacent Duplicates In String
- problem 1089: Duplicate Zeros
- problem 151: Reverse Words in a String
- problem 187: Repeated DNA Sequences
- problem 51: N-Queens
- problem 52: N-Queens II
- problem 68: Text Justification
- problem 76: Minimum Window Substring
- problem 135: Candy
- problem 140: Word Break II
- problem 220: Contains Duplicate III
- problem 239: Sliding Window Maximum
- problem 352: Data Stream as Disjoint Intervals
- problem 502: IPO
- problem 895: Maximum Frequency Stack
- problem 982: Triples with Bitwise AND Equal To Zero
- problem 995: Minimum Number of K Consecutive Bit Flips
- problem 996: Number of Squareful Arrays
- problem 2136: Earliest Possible Day of Full Bloom
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality