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.
To solve the problem, we consider the possible paths to the destination using combinatorial logic. The objective in this approach is to determine if a 'H' or 'V' should be appended next based on how many sequences remain. We use combinations to count these sequences instead of generating them explicitly. The binomial coefficient helps decide if the next letter should be an 'H' or a 'V', and thereby decide the kth path without having to construct all possible paths:
This Python solution uses the combinatorial library to calculate the number of ways remaining to complete a path. Initially, it attempts to append an 'H'. If the number of ways exceeds k, it appends 'H'; otherwise, it appends 'V'. This decision process is repeated until the destination is reached.
Time Complexity: O(n + m), where n is the number of rows and m is the number of columns. Each step either appends 'H' or 'V'.
Space Complexity: O(n + m) for storing the path string.
The dynamic programming approach involves creating a 2D table that keeps track of the number of ways paths can be constructed to reach certain coordinates. This table helps us quickly decide if the nth or kth smallest lexicographic sequence favors a horizontal or vertical move:
This Java solution precomputes the number of ways to reach each coordinate using a dynamic programming table. It efficiently decides the next move by checking the number of ways remaining in a coordinated direction. This ensures correct lexicographic path selection according to k.
Java
JavaScript
Time Complexity: O(n * m), where n is the number of rows and m is the number of columns. This is due to filling the DP table.
Space Complexity: O(n * m), for the DP table storage.
| Approach | Complexity |
|---|---|
| Combinatorial Approach | Time Complexity: O(n + m), where n is the number of rows and m is the number of columns. Each step either appends 'H' or 'V'. Space Complexity: O(n + m) for storing the path string. |
| Dynamic Programming Approach | Time Complexity: O(n * m), where n is the number of rows and m is the number of columns. This is due to filling the DP table. Space Complexity: O(n * m), for the DP table storage. |
| Default Approach | — |
| 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 |
Leetcode 1643. Kth Smallest Instructions • Fraz • 7,040 views views
Watch 8 more video solutions →Practice Kth Smallest Instructions with our built-in code editor and test cases.
Practice on FleetCode