In this guide, you will get 1643. Kth Smallest Instructions LeetCode Solution with the best time and space complexity. The solution to Kth Smallest Instructions problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Bob is standing at cell (0, 0), and he wants to reach destination: (row, column). He can only travel right and down. You are going to help Bob by providing instructions for him to reach destination.
The instructions are represented as a string, where each character is either:
‘H’, meaning move horizontally (go right), or
‘V’, meaning move vertically (go down).
Multiple instructions will lead Bob to destination. For example, if destination is (2, 3), both “HHHVV” and “HVHVH” are valid instructions.
However, Bob is very picky. Bob has a lucky number k, and he wants the kth lexicographically smallest instructions that will lead him to destination. k is 1-indexed.
Given an integer array destination and an integer k, return the kth lexicographically smallest instructions that will take Bob to destination.
Example 1:
Input: destination = [2,3], k = 1
Output: “HHHVV”
Explanation: All the instructions that reach (2, 3) in lexicographic order are as follows:
[“HHHVV”, “HHVHV”, “HHVVH”, “HVHHV”, “HVHVH”, “HVVHH”, “VHHHV”, “VHHVH”, “VHVHH”, “VVHHH”].
destination.length == 2
1 <= row, column <= 15
1 <= k <= nCr(row + column, row), where nCr(a, b) denotes a choose b.
Complexity Analysis
Time Complexity: O(\texttt{row}(\texttt{column} + \texttt{row}))
Space Complexity: O(\texttt{row}(\texttt{column} + \texttt{row}))
1643. Kth Smallest Instructions LeetCode Solution in C++
class Solution {
public:
string kthSmallestPath(vector<int>& destination, int k) {
string ans;
int v = destination[0];
int h = destination[1];
const int totalSteps = v + h;
const vector<vector<int>> comb = getComb(totalSteps - 1, v);
for (int i = 0; i < totalSteps; ++i) {
// If 'H' is picked, we can reach ranks [1, availableRank].
const int availableRank = comb[h + v - 1][v];
if (availableRank >= k) { // Should pick 'H'.
ans += 'H';
--h;
} else { // Should pick 'V'.
k -= availableRank;
ans += 'V';
--v;
}
}
return ans;
}
private:
// C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
vector<vector<int>> getComb(int n, int k) {
vector<vector<int>> comb(n + 1, vector<int>(k + 1));
for (int i = 0; i <= n; ++i)
comb[i][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= k; ++j)
comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
return comb;
}
}; /* code provided by PROGIEZ */
1643. Kth Smallest Instructions LeetCode Solution in Java
class Solution {
public String kthSmallestPath(int[] destination, int k) {
StringBuilder sb = new StringBuilder();
int v = destination[0];
int h = destination[1];
final int totalSteps = v + h;
final int[][] comb = getComb(totalSteps - 1, v);
for (int i = 0; i < totalSteps; ++i) {
// If 'H' is picked, we can reach ranks [1, availableRank].
final int availableRank = comb[h + v - 1][v];
if (availableRank >= k) { // Should pick 'H'.
sb.append('H');
--h;
} else { // Should pick 'V'.
k -= availableRank;
sb.append('V');
--v;
}
}
return sb.toString();
}
private int[][] getComb(int n, int k) {
int[][] comb = new int[n + 1][k + 1];
for (int i = 0; i <= n; ++i)
comb[i][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= k; ++j)
comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
return comb;
}
} // code provided by PROGIEZ
1643. Kth Smallest Instructions LeetCode Solution in Python
class Solution:
def kthSmallestPath(self, destination: list[int], k: int) -> str:
ans = []
v, h = destination
for _ in range(h + v):
# If pick 'H', then we're able to reack 1, 2, ..., availableRank.
availableRank = math.comb(h + v - 1, v)
if availableRank >= k: # Should pick 'H'.
ans.append('H')
h -= 1
else: # Should pick 'V'.
k -= availableRank
ans.append('V')
v -= 1
return ''.join(ans) # code by PROGIEZ
