Problem 60

Abstract / Summary

Given n and k return the kth sequence in the list of all possible orderings of numbers from one to n without repeats

Note

The full problem description, including helpful examples, can be found on LeetCode.

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;
    }
};
14 lines | 291 bytes | submitted August 9, 2023 | GitHub   9% comment ratio | tab size 4

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 54% (1+ million submissions).

Typical patterns to solve this problem:
  • Math
  • Recursion
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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_permutation rearranges 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 k is 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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 4 | μ = 4.52 | σ = 1.93

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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++
47 links | 31 authors | 9 languages

Videos

8 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

10 easy 2 medium 15 hard
28 solutions   August 9, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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