1643. Kth Smallest Instructions
Problem Description
Bob starts from cell (0, 0)
and wants to reach the destination
at (row, column)
. He can only go right, denoted with H
, or down, denoted with V
. We need to give Bob a set of instructions that not only gets him to destination
but also ensures that this set of instructions is the kth
lexicographically smallest sequence possible.
Bob is picky and wants only the kth
lexicographically smallest instructions, where k
is 1-indexed. This means that if all possible correct sequences of instructions are sorted lexicographically, Bob wants the k-th sequence in this sorted order.
The destination
is given in the form of an integer array [v, h]
where v
represents the vertical moves Bob needs to make downwards, and h
represents the horizontal moves Bob needs to make to the right. In the case that destination
is (2, 3)
, he needs to go down twice (VV
) and right three times (HHH
). The combinations HHHVV
, HVHVH
, VHHHV
, etc., are different ways to arrange these moves.
Intuition
The solution is based on understanding combinatorics and lexicographical ordering. We base our solution on the facts that:
-
There are
comb(h + v, h)
ways to arrangeh
horizontal moves andv
vertical moves, withh + v
being the total number of moves made. -
A lexicographically smaller sequence starts with the smallest possible character, which is
H
in this case.
So the intuition behind the solution is as follows:
- We initialize the moves by calculating the total possible combinations to reach the destination given the current number of horizontal
h
and verticalv
moves remaining. This is done using the combinatorial functioncomb
. - At every step, we decide whether to place an
H
or aV
. If we place anH
, we reduce the number of horizontal moves, and if we place aV
, we reduce the vertical moves. - We check if the remaining combinations after placing an
H
are less thank
. If they are, it means that adding anH
would not reach the k-th sequence. In such a case, we must add aV
, decrementv
, and adjustk
by subtracting the number of sequences that would've started with anH
. - If the remaining combinations after placing an
H
are more or equal tok
, it means anH
can be added to the sequence without surpassing the k-th smallest requirement. - We repeat this process until we run out of either horizontal or vertical moves.
- As
H
is lexicographically smaller thanV
, we aim to addH
whenever possible, following the rules above to respect the k-th smallest condition.
By iterating through all moves and following this process, we construct the kth
smallest lexicographical sequence that leads Bob to his destination.
Learn more about Math, Dynamic Programming and Combinatorics patterns.
Solution Approach
The implementation is straightforward given our understanding of the intuition behind the problem. Here's a step-by-step explanation of the approach:
-
We begin by identifying the number of vertical and horizontal moves required to reach the destination,
v
andh
respectively. -
Define a string list
ans
which will hold the sequence of moves. -
Iterate through the combined number of moves (
h + v
). -
If there are no horizontal moves left (
h
is 0), we can only move down. So we addV
toans
and continue. -
Otherwise, calculate the current number of combinations with
x = comb(h + v - 1, h - 1)
. This represents the number of ways to arrange remaining moves if the next move is horizontal. -
Compare
x
withk
. Ifk
is larger, it means that the k-th sequence is not in the group of sequences that start with anH
followed by all possible combinations of the remaining moves. Therefore, addV
toans
, decrementv
, and subtractx
fromk
to reflect that we skip all those combinations that start withH
. -
If
k
is not larger thanx
, it means that the k-th sequence does start with anH
followed by the remaining moves. In this case, addH
toans
and decrementh
. -
After the loop,
ans
will contain the k-th lexicographically smallest instruction set.
In terms of algorithms, data structures, and patterns, we are using:
-
String/List manipulation: We use a list
ans
to build the sequence incrementally. The list is then converted to a string at the end. -
Combinatorics: By using the combinatorial function
comb
, we calculate the number of ways to arrange the remaining moves. -
Decision-making under constraints: At each step, the decision to add
H
orV
is made based on the number of combinations remaining and the value ofk
. -
Greedy approach: At each step, we take the locally optimal choice (adding
H
if possible) to reach the global optimization (k-th smallest sequence) while iterating through the process.
The code given in the solution efficiently performs this approach and keeps track of the sequence to be returned.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with an example where Bob has to reach a destination
at (2, 3)
and wants the 3rd lexicographically smallest sequence of instructions. This means v = 2
for downwards moves and h = 3
for rightwards moves, and k = 3
.
-
Bob needs 2
V
moves and 3H
moves. The possible sequences, sorted lexicographically, are:HHHVV
HHVHV
HHVVH
HVHHV
HVHVH
HVVHH
VHHHV
VHHVH
VHVHH
VVHHH
-
Given the above sequences, we can see that the 3rd sequence is
HHVVH
. We will achieve the same result following our solution approach. -
Begin with
h = 3
,v = 2
, andk = 3
. Listans
is currently empty. -
At the starting point (
h + v = 5
moves remaining), we calculate the combinations possible with the first move beingH
, which iscomb(4,2) = 6
. This number indicates the count of sequences beginning withH
. -
Comparing
x
(6) withk
(3), sincek
is less thanx
, we addH
toans
and decrementh
to 2 (h + v = 4
moves remaining). -
We again calculate
x = comb(3, 2) = 3
for the possibility of the next move beingH
. -
k
equalsx
, so adding anH
is still valid. We add anotherH
and decrementh
to 1 (h + v = 3
moves remaining). -
Calculate
x = comb(2, 1) = 2
. Sincex
is less thank
(which is still 3), we cannot add anH
because we need to find the 3rd sequence, and there are only 2 sequences starting withHHH
. We addV
toans
, decrementv
to 1, and updatek
tok - x = 1
(h + v = 2
moves remaining). -
Now, calculate
x = comb(1, 1) = 1
for the possibility of the next move beingH
. -
Since
k
(1) equalsx
(1), we can addH
. We addH
toans
, decrementh
to 0 (h + v = 1
move remaining). -
With only one move remaining and
h
being 0, we add the finalV
. -
Now
ans
holdsHHVVH
, which is the 3rd lexicographically smallest sequence of instructions for Bob to reach(2, 3)
.
By following each step of our solution approach, we've successfully assembled the 3rd lexicographically smallest set of instructions for Bob's journey to the destination.
Solution Implementation
1from math import comb
2from typing import List
3
4class Solution:
5 def kthSmallestPath(self, destination: List[int], k: int) -> str:
6 vertical, horizontal = destination
7 answer = []
8
9 # Loop through the total number of moves (sum of vertical and horizontal moves)
10 for _ in range(horizontal + vertical):
11 # If there are no more horizontal moves, all remaining moves are vertical
12 if horizontal == 0:
13 answer.append("V")
14 else:
15 # Calculate the number of combinations that start with a horizontal move
16 combinations_with_h = comb(horizontal + vertical - 1, horizontal - 1)
17
18 # If the kth path is greater than the number of paths starting with 'H',
19 # then the path must start with a 'V' move instead.
20 if k > combinations_with_h:
21 answer.append("V")
22 vertical -= 1
23 k -= combinations_with_h
24 else:
25 # Otherwise, the path starts with a 'H' move
26 answer.append("H")
27 horizontal -= 1
28
29 # Join all moves into a single path string and return it
30 return "".join(answer)
31
1class Solution {
2 public String kthSmallestPath(int[] destination, int k) {
3 int verticalSteps = destination[0];
4 int horizontalSteps = destination[1];
5 int totalSteps = verticalSteps + horizontalSteps;
6
7 // Create a combination lookup table where c[i][j] represents the number
8 // of combinations of i elements taken j at a time
9 int[][] combinations = new int[totalSteps + 1][horizontalSteps + 1];
10
11 // Base case: there is 1 way to choose 0 items out of i
12 combinations[0][0] = 1;
13 for (int i = 1; i <= totalSteps; ++i) {
14 combinations[i][0] = 1;
15 for (int j = 1; j <= horizontalSteps; ++j) {
16 // Calculate the combination count using Pascal's triangle relationship
17 combinations[i][j] = combinations[i - 1][j] + combinations[i - 1][j - 1];
18 }
19 }
20
21 // Build the path using the combination count to make decisions
22 StringBuilder path = new StringBuilder();
23 for (int i = totalSteps; i > 0; --i) {
24 // If no horizontal steps are left, we must take a vertical step
25 if (horizontalSteps == 0) {
26 path.append('V');
27 } else {
28 // Check how many combinations would there be if we took a horizontal step first;
29 // this helps determine if kth path starts with 'H' or 'V' given the remaining steps
30 int combinationsIfHFirst = combinations[verticalSteps + horizontalSteps - 1][horizontalSteps - 1];
31 if (k > combinationsIfHFirst) {
32 // If 'k' is larger than the number of combinations with 'H' first,
33 // the kth path must start with 'V'. We subtract the combinations and reduce the vertical step
34 path.append('V');
35 k -= combinationsIfHFirst;
36 --verticalSteps;
37 } else {
38 // Otherwise, we append 'H' to our path and reduce the horizontal step
39 path.append('H');
40 --horizontalSteps;
41 }
42 }
43 }
44
45 // Return the constructed path as a string
46 return path.toString();
47 }
48}
49
1class Solution {
2public:
3 // Function to find the k-th smallest path in a grid given the destination.
4 string kthSmallestPath(vector<int>& destination, int k) {
5 int v = destination[0]; // Vertical moves required
6 int h = destination[1]; // Horizontal moves required
7 int n = v + h; // Total moves required
8
9 // Initialize combinatorial lookup table to store the binomial coefficients
10 int comb[n + 1][h + 1];
11 memset(comb, 0, sizeof(comb)); // Fill the array with zeroes
12 comb[0][0] = 1;
13
14 // Populate the table with binomial coefficients using Pascal's Triangle
15 for (int i = 1; i <= n; ++i) {
16 comb[i][0] = 1;
17 for (int j = 1; j <= h; ++j) {
18 comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
19 }
20 }
21
22 string ans; // String to hold the result
23
24 // Construct the lexicographically k-th smallest path
25 for (int i = 0; i < n; ++i) {
26 if (h == 0) { // If no more horizontal moves, then move vertical
27 ans.push_back('V');
28 } else {
29 // Find the number of sequences starting with 'H'
30 int countHStart = comb[v + h - 1][h - 1];
31
32 // If k is greater than countHStart, then the current move must be 'V'
33 if (k > countHStart) {
34 ans.push_back('V');
35 --v; // One less vertical move needed
36 k -= countHStart; // Reduce k by the number of sequences counted
37 } else {
38 // If k is within the range, the current move is 'H'
39 ans.push_back('H');
40 --h; // One less horizontal move needed
41 }
42 }
43 }
44
45 return ans; // Return the constructed path
46 }
47};
48
1function kthSmallestPath(destination: number[], k: number): string {
2 let verticalMoves = destination[0]; // Vertical moves required
3 let horizontalMoves = destination[1]; // Horizontal moves required
4 let totalMoves = verticalMoves + horizontalMoves; // Total moves required
5
6 // Initialize combinatorial lookup table to store the binomial coefficients
7 let comb: number[][] = Array.from({ length: totalMoves + 1 }, () => Array(horizontalMoves + 1).fill(0));
8 comb[0][0] = 1;
9
10 // Populate the table with binomial coefficients using Pascal's Triangle
11 for (let i = 1; i <= totalMoves; ++i) {
12 comb[i][0] = 1;
13 for (let j = 1; j <= horizontalMoves; ++j) {
14 comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
15 }
16 }
17
18 let path = ''; // String to hold the result
19
20 // Construct the lexicographically k-th smallest path
21 for (let i = 0; i < totalMoves; ++i) {
22 if (horizontalMoves === 0) { // If no more horizontal moves, then move vertically
23 path += 'V';
24 continue;
25 }
26
27 // Find the number of sequences starting with 'H'
28 let countHStart = comb[verticalMoves + horizontalMoves - 1][horizontalMoves - 1];
29
30 // If k is greater than countHStart, then the current move must be 'V'
31 if (k > countHStart) {
32 path += 'V';
33 verticalMoves--; // One less vertical move is needed
34 k -= countHStart; // Reduce k by the number of sequences counted
35 } else {
36 // If k is within the range, the current move is 'H'
37 path += 'H';
38 horizontalMoves--; // One less horizontal move is needed
39 }
40 }
41
42 return path; // Return the constructed path
43}
44
45// Test the function with a sample input
46let destinationSample = [2, 3];
47let kSample = 3;
48console.log(kthSmallestPath(destinationSample, kSample)); // Outputs the k-th smallest path in string format
49
Time and Space Complexity
Time Complexity
The main operation of this algorithm is conducted within a loop that iterates (h + v)
times, where h
and v
are the numbers of horizontal and vertical steps to reach the destination, respectively.
Within this loop, the time-critical step is the computation of combinations using comb(h + v - 1, h - 1)
to decide whether to add "H" or "V" to the path. The comb
function's complexity can vary depending on the implementation, but generally, it is computed using factorials which can be intensive. However, since Python's comb
function uses an efficient algorithm presumably based on Pascal's triangle or multiplicative formula, we can assume it runs in O(r) or O(n-r) time complexity, where n
is the first argument and r
is the second argument to comb
.
In the worst-case scenario, we are looking at:
- A time complexity of O(h * min(h, v)) for computing the combination when
v
>=h
, becausecomb(h + v - 1, h - 1)
simplifies tocomb(h + v - 1, v)
whenv < h
. Since the loop runsh + v
times and the most time-consuming operation is O(min(h, v)), the overall time complexity would be O((h + v) * min(h, v)).
Space Complexity
The space complexity is determined by the storage used for the ans
list. Since the ans
list will contain at most (h + v)
characters, the space complexity is O(h + v).
Learn more about how to find time and space complexity quickly using problem constraints.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
Want a Structured Path to Master System Design Too? Donāt Miss This!