Is Kth Smallest Instructions easy or hard?

The problem is rated Hard on LeetCode because it requires recognizing the combinatorial structure of the paths and using lexicographic ranking logic. Once the binomial counting insight is clear, the implementation becomes relatively straightforward.

Kth Smallest Instructions Python/Java solution

Python and Java implementations typically precompute combination values using a 2D array. Then a greedy loop builds the result string by comparing k with the number of sequences that begin with 'H'. The same logic works in C++, JavaScript, and other languages.

How to solve Kth Smallest Instructions in O(n)?

After precomputing combination values, building the instruction string is O(n) where n = row + col. At each step you check C(remainingMoves-1, remainingH-1) to decide whether the next character should be 'H' or 'V'. This greedy selection skips large groups of sequences at once.

What is the best approach for Kth Smallest Instructions?

The combinatorial greedy approach is the most efficient and commonly expected solution. At each step you count how many paths start with 'H' using the binomial coefficient C(row+col-1, col-1). If k is within that range, choose 'H'; otherwise choose 'V' and subtract the skipped count. This constructs the k-th lexicographic sequence without generating all paths.

Is Kth Smallest Instructions asked at Google/Amazon/Meta?

Problems involving combinatorics and lexicographic ordering frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include k-th permutation, k-th lexicographic path, or counting grid paths with constraints.

What data structure is used in Kth Smallest Instructions?

The solution primarily relies on combinatorics and counting rather than complex data structures. Most implementations use a 2D array for Pascal's triangle or a DP table to store binomial coefficients and path counts.

What is the time complexity of Kth Smallest Instructions?

The typical solution precomputes binomial coefficients using Pascal's triangle in O((row+col)^2) time and space. Constructing the final instruction string then takes O(row+col). Overall complexity is dominated by the combination preprocessing step.

Description Hints 2 Solution Video 11:20

1643. Kth Smallest Instructions

Hard44.7% acceptance1 company

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 k^th lexicographically smallest instructions that will lead him to destination. k is 1-indexed.

Given an integer array destination and an integer k, return the k^th 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 == 2
1 <= row, column <= 15
1 <= k <= nCr(row + column, row), where nCr(a, b) denotes a choose b.

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

There are nCr(row + column, row) possible instructions to reach (row, column).

Hint 2

Try building the instructions one step at a time. How many instructions start with "H", and how does this compare with k?

11:20

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def kthSmallestPath(self, destination: List[int], k: int) -> str:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[2,3]
1

Input

[2,3]
2

Input

[2,3]
3

Your code is saved on this device.Solution