Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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"].
Example 2:
Input: destination = [2,3], k = 2 Output: "HHVHV"
Example 3:
Input: destination = [2,3], k = 3 Output: "HHVVH"
Constraints:
destination.length == 21 <= row, column <= 151 <= k <= nCr(row + column, row), where nCr(a, b) denotes a choose b.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Math · Dynamic Programming
[2,3] 1
[2,3] 2
[2,3] 3
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1643: Kth Smallest Instructions
class Solution {
public String kthSmallestPath(int[] destination, int k) {
int v = destination[0], h = destination[1];
int n = v + h;
int[][] c = new int[n + 1][h + 1];
c[0][0] = 1;
for (int i = 1; i <= n; ++i) {
c[i][0] = 1;
for (int j = 1; j <= h; ++j) {
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
StringBuilder ans = new StringBuilder();
for (int i = n; i > 0; --i) {
if (h == 0) {
ans.append('V');
} else {
int x = c[v + h - 1][h - 1];
if (k > x) {
ans.append('V');
k -= x;
--v;
} else {
ans.append('H');
--h;
}
}
}
return ans.toString();
}
}
// Accepted solution for LeetCode #1643: Kth Smallest Instructions
func kthSmallestPath(destination []int, k int) string {
v, h := destination[0], destination[1]
n := v + h
c := make([][]int, n+1)
for i := range c {
c[i] = make([]int, h+1)
c[i][0] = 1
}
for i := 1; i <= n; i++ {
for j := 1; j <= h; j++ {
c[i][j] = c[i-1][j] + c[i-1][j-1]
}
}
ans := []byte{}
for i := 0; i < n; i++ {
if h == 0 {
ans = append(ans, 'V')
} else {
x := c[v+h-1][h-1]
if k > x {
ans = append(ans, 'V')
k -= x
v--
} else {
ans = append(ans, 'H')
h--
}
}
}
return string(ans)
}
# Accepted solution for LeetCode #1643: Kth Smallest Instructions
class Solution:
def kthSmallestPath(self, destination: List[int], k: int) -> str:
v, h = destination
ans = []
for _ in range(h + v):
if h == 0:
ans.append("V")
else:
x = comb(h + v - 1, h - 1)
if k > x:
ans.append("V")
v -= 1
k -= x
else:
ans.append("H")
h -= 1
return "".join(ans)
// Accepted solution for LeetCode #1643: Kth Smallest Instructions
struct Solution;
impl Solution {
fn kth_smallest_path(destination: Vec<i32>, k: i32) -> String {
let n = (destination[0] + 1) as usize;
let m = (destination[1] + 1) as usize;
let mut res = "".to_string();
let mut dp = vec![vec![0; m]; n];
for i in (0..n).rev() {
for j in (0..m).rev() {
if i == n - 1 && j == m - 1 {
dp[i][j] = 1;
continue;
}
if i == n - 1 {
dp[i][j] = dp[i][j + 1];
continue;
}
if j == m - 1 {
dp[i][j] = dp[i + 1][j];
continue;
}
dp[i][j] = dp[i][j + 1] + dp[i + 1][j];
}
}
Self::build(0, 0, k, &mut res, &dp, n, m);
res
}
fn build(i: usize, j: usize, k: i32, path: &mut String, dp: &[Vec<i32>], n: usize, m: usize) {
if i == n - 1 && j == m - 1 {
return;
}
if i == n - 1 {
path.push('H');
Self::build(i, j + 1, k, path, dp, n, m);
return;
}
if j == m - 1 {
path.push('V');
Self::build(i + 1, j, k, path, dp, n, m);
return;
}
if k <= dp[i][j + 1] {
path.push('H');
Self::build(i, j + 1, k, path, dp, n, m);
} else {
path.push('V');
Self::build(i + 1, j, k - dp[i][j + 1], path, dp, n, m);
}
}
}
#[test]
fn test() {
let destination = vec![2, 3];
let k = 1;
let res = "HHHVV".to_string();
assert_eq!(Solution::kth_smallest_path(destination, k), res);
let destination = vec![2, 3];
let k = 2;
let res = "HHVHV".to_string();
assert_eq!(Solution::kth_smallest_path(destination, k), res);
let destination = vec![2, 3];
let k = 3;
let res = "HHVVH".to_string();
assert_eq!(Solution::kth_smallest_path(destination, k), res);
}
// Accepted solution for LeetCode #1643: Kth Smallest Instructions
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1643: Kth Smallest Instructions
// class Solution {
// public String kthSmallestPath(int[] destination, int k) {
// int v = destination[0], h = destination[1];
// int n = v + h;
// int[][] c = new int[n + 1][h + 1];
// c[0][0] = 1;
// for (int i = 1; i <= n; ++i) {
// c[i][0] = 1;
// for (int j = 1; j <= h; ++j) {
// c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
// }
// }
// StringBuilder ans = new StringBuilder();
// for (int i = n; i > 0; --i) {
// if (h == 0) {
// ans.append('V');
// } else {
// int x = c[v + h - 1][h - 1];
// if (k > x) {
// ans.append('V');
// k -= x;
// --v;
// } else {
// ans.append('H');
// --h;
// }
// }
// }
// return ans.toString();
// }
// }
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.