Watch 9 video solutions for Kth Smallest Instructions, a hard level problem involving Array, Math, Dynamic Programming. This walkthrough by Fraz has 7,040 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 Overview: You are given a grid destination [row, col]. Starting from (0,0), you must reach the destination using only H (right) and V (down) moves. Among all valid instruction strings, return the k-th smallest in lexicographic order. The total length of the string is row + col, containing exactly row V's and col H's.
Approach 1: Dynamic Programming Counting (O(row * col) time, O(row * col) space)
The key observation: instead of generating all paths, count how many paths start with a particular move. Use dynamic programming to compute the number of ways to reach the destination from every cell. Let dp[r][c] represent the number of valid paths from that position to the destination. The recurrence is straightforward: dp[r][c] = dp[r+1][c] + dp[r][c+1]. When constructing the answer, try placing H first because it is lexicographically smaller. If the number of paths starting with H is at least k, append H. Otherwise append V and subtract that count from k. Continue until all moves are placed. This approach explicitly models the grid and is easy to reason about using dynamic programming.
Approach 2: Combinatorial Greedy (O((row + col)^2) time, O((row + col)^2) space)
A more mathematical view treats the path as arranging characters. Any valid path is a permutation of row V's and col H's. The number of paths starting with H equals the number of ways to arrange the remaining characters: C(row + col - 1, col - 1). Compute binomial coefficients using Pascal's triangle or a combination table. At each step, check how many sequences start with H. If k is less than or equal to that count, append H. Otherwise append V and reduce k by that count. Decrease the remaining counts and repeat. This approach avoids storing a grid and relies on combinatorics and greedy decision making.
The algorithm effectively performs lexicographic ranking of sequences with fixed character counts. Each decision narrows the search space by skipping entire groups of sequences using combinatorial counts rather than enumeration.
Recommended for interviews: The combinatorial greedy approach is the expected solution. It shows that you recognize the path count as a binomial coefficient and can construct the k-th sequence directly. Explaining the DP counting version first can help demonstrate understanding, but interviewers usually want the optimized reasoning using math and combinations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming Counting | O(row * col) | O(row * col) | When you want a clear grid-based interpretation and straightforward implementation |
| Combinatorial Greedy | O((row + col)^2) | O((row + col)^2) | Preferred solution for interviews; directly computes lexicographic order using combinations |