Kth Smallest Instructions — Solution in Python, Java & C++
Kth Smallest Instructions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Kth Smallest Instructions is a hard coding problem on arrays, dynamic programming and math, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Math, Combinatorics
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A robot starts at cell (0, 0) and must reach destination = [row, column]. It can only move right, written 'H', or down, written 'V', so every route is a string of column letters 'H' and row letters 'V'.
Order all such strings lexicographically ('H' comes before 'V'). Given k, return the k-th string in that order (1-indexed).
Example 1
Input: destination = [2,2], k = 4
Output: VHHV
Explanation: The six routes in order are HHVV, HVHV, HVVH, VHHV, VHVH, VVHH.
Example 2
Input: destination = [1,3], k = 2
Output: HHVH
Example 3
Input: destination = [2,3], k = 1
Output: HHHVV
Constraints
destination.length == 21 <= row, column <= 151 <= k <= nCr(row + column, row)
Hints for Kth Smallest Instructions
Hint 1
Build the answer one letter at a time, deciding whether it starts with
'H'or'V'.Hint 2
If
hmoves right andvmoves down remain, exactlyC(h - 1 + v, v)of the remaining routes start with'H'.Hint 3
If
kis at most that count, write'H'; otherwise write'V'and subtract the count fromk.
How to solve Kth Smallest Instructions
Lexicographic ranking by counting: every route that starts with 'H' comes before every route that starts with 'V', and the number of routes beginning with 'H' is a binomial coefficient. So each letter is decided by comparing k with one count.
Approach
- Precompute Pascal's triangle up to 30 (
C(30, 15)still fits in 32 bits). - Let
h = column,v = row. While letters remain: ifh > 0, letc = C(h - 1 + v, v), the number of completions after an'H'. - If
h > 0andk <= c, append'H'and decrementh. Otherwise append'V', subtractc(0 whenh == 0) fromk, and decrementv.
Why it works
At each step the remaining routes split into a block starting with 'H' followed by a block starting with 'V'. If the k-th route lies in the first block (k <= c) its next letter is 'H' and its rank inside that block is still k; otherwise its next letter is 'V' and its rank inside the second block is k - c. The invariant "the answer is the k-th route of the remaining grid" holds to the end.
Complexity
- Time —
O(row + column) - Space —
O(1) beyond the 31-row Pascal table
Pitfalls
'H'(right) consumes the column count and sorts first; it is easy to swap the roles ofrowandcolumn.- When
hreaches 0 the rest of the answer is all'V'— guard the binomial lookup so it does not readC(v - 1, v). kis 1-indexed: the first route isk = 1.
Reference solution
Python
from typing import List
from math import comb
def kthSmallestPath(destination: List[int], k: int) -> str:
v, h = destination
out = []
while h + v > 0:
start_h = comb(h - 1 + v, v) if h > 0 else 0 # routes that begin with 'H'
if h > 0 and k <= start_h:
out.append('H')
h -= 1
else:
out.append('V')
k -= start_h
v -= 1
return ''.join(out)Java
public static String kthSmallestPath(int[] destination, int k) {
int[][] comb = new int[31][31];
for (int i = 0; i <= 30; i++) {
comb[i][0] = comb[i][i] = 1;
for (int j = 1; j < i; j++) comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
}
int v = destination[0], h = destination[1];
StringBuilder out = new StringBuilder();
while (h + v > 0) {
int startH = h > 0 ? comb[h - 1 + v][v] : 0; // routes that begin with 'H'
if (h > 0 && k <= startH) {
out.append('H');
h--;
} else {
out.append('V');
k -= startH;
v--;
}
}
return out.toString();
}C++
string kthSmallestPath(vector<int>& destination, int k) {
vector<vector<int>> comb(31, vector<int>(31, 0));
for (int i = 0; i <= 30; i++) {
comb[i][0] = comb[i][i] = 1;
for (int j = 1; j < i; j++) comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
}
int v = destination[0], h = destination[1];
string out;
while (h + v > 0) {
int startH = h > 0 ? comb[h - 1 + v][v] : 0; // routes that begin with 'H'
if (h > 0 && k <= startH) {
out += 'H';
h--;
} else {
out += 'V';
k -= startH;
v--;
}
}
return out;
}JavaScript
var kthSmallestPath = function(destination, k) {
var comb = [];
for (var i = 0; i <= 30; i++) {
comb.push([]);
for (var j = 0; j <= i; j++) comb[i].push(j === 0 || j === i ? 1 : comb[i - 1][j - 1] + comb[i - 1][j]);
}
var v = destination[0], h = destination[1];
var out = "";
while (h + v > 0) {
var startH = h > 0 ? comb[h - 1 + v][v] : 0; // routes that begin with 'H'
if (h > 0 && k <= startH) {
out += "H";
h--;
} else {
out += "V";
k -= startH;
v--;
}
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming