Kth Smallest Instructions: Combinatorial Path Counting

You are given a destination [row, col] in a grid and an integer k. Starting from (0, 0), you can only move right (H) or down (V). Every path to the destination uses exactly col H moves and row V moves, forming a string of length row + col. Return the kth smallest instruction string in lexicographic order.

This is LeetCode 1643: Kth Smallest Instructions. If you have solved Unique Paths, you already know that the total number of paths from (0, 0) to (row, col) equals C(row + col, col). This problem builds on that idea: instead of counting all paths, you need to find one specific path by its position in sorted order.

For destination = [2, 3] and k = 1, the output is "HHHVV". That is the lexicographically smallest string with 3 H's and 2 V's, because H comes before V and placing all H's first produces the smallest ordering.

Why this problem matters

Kth Smallest Instructions combines two ideas that appear across many problems: combinatorial counting and lexicographic ordering. The counting piece uses the binomial coefficient, the same tool behind Unique Paths and Combinations. The ordering piece uses a greedy character-by-character construction, the same strategy behind Permutation Sequence.

Problems that ask "find the kth element in some ordering" show up frequently in interviews. The brute-force approach (generate all elements, sort, pick the kth) is almost always too slow. The efficient approach is to use counting to skip over entire groups without generating them. Once you internalize this counting-and-skipping strategy, you can apply it to permutations, combinations, paths, and many other structured sequences.

The key insight

Since H comes before V lexicographically, all paths that start with H appear before all paths that start with V. This means you can decide the first character by counting how many paths start with H:

1. If you place H first, the remaining (row + col - 1) moves need (col - 1) H's and row V's. The count of such paths is C(row + col - 1, col - 1).
2. If that count is at least k, the kth path starts with H. Move right and keep searching for the same k in the smaller subproblem.
3. If that count is less than k, the kth path starts with V. Subtract the count from k (to skip past all the H-first paths), move down, and continue.

Repeat this at every position until you have placed all row + col characters. Each step reduces the problem by one character, and the combination count tells you exactly which branch to take.

The solution

from math import comb

def kthSmallestPath(destination: list[int], k: int) -> str:
    row, col = destination
    result = []

    for _ in range(row + col):
        if col > 0:
            count = comb(row + col - 1, col - 1)
            if k <= count:
                result.append("H")
                col -= 1
            else:
                k -= count
                result.append("V")
                row -= 1
        else:
            result.append("V")
            row -= 1

    return "".join(result)

Let's break this down.

The function starts with row and col from the destination, which tell you how many V and H moves remain. At each iteration, you decide whether the next character is H or V.

If col > 0, you compute count = comb(row + col - 1, col - 1). This is the number of paths where the next move is H: after placing one H, you have (row + col - 1) moves left with (col - 1) of them being H. If k is within this count, you pick H and decrement col. Otherwise, you skip past all those H-first paths by subtracting count from k, pick V, and decrement row.

If col is already 0, you have no H moves left, so the only option is V.

The result string accumulates one character per iteration. After row + col iterations, every move has been decided and you return the joined string.

Visual walkthrough

Let's trace through destination = [2, 3] and k = 3. There are C(5, 3) = 10 total paths. We want the 3rd lexicographically smallest.

The final answer is "HHVVH". At each step, the combination count tells you whether to go right (H) or down (V). When the count is large enough, you stay in the H group. When it is too small, you skip past the H group and enter the V group.

Complexity analysis

Time is O(row + col). The loop runs exactly row + col iterations, one for each character in the output. Each iteration computes one binomial coefficient, which takes O(1) with Python's built-in comb (or O(min(row, col)) if you compute it manually). Either way, the total work is linear in the path length.

Space is O(row + col) for the result string. No recursion, no 2D table, and no sorted list of all paths. Just a single pass building the answer character by character.

The building blocks

This problem is built on two core reusable pieces that CodeBricks drills independently.

Binomial coefficient for path counting

The number of ways to arrange h H's and v V's in a string of length h + v is C(h + v, h). This is the same formula that gives the number of grid paths in Unique Paths. Whenever a problem involves choosing positions for one type of item among a fixed total, the binomial coefficient is the counting tool.

from math import comb

total_paths = comb(row + col, col)

You use this building block every time you need to count how many sequences remain after fixing one character. The formula C(remaining - 1, h - 1) counts the paths that start with H, because you lock in one H and count the arrangements of everything else.

Greedy lexicographic construction

The strategy of building the kth element one character at a time by counting how many options fall in each group is a general pattern. You saw it in Permutation Sequence, where you divide k by factorials to pick each digit. Here, you divide using binomial coefficients instead of factorials, but the structure is identical:

if k <= count_of_first_option:
    pick_first_option()
else:
    k -= count_of_first_option
    pick_second_option()

This "count and skip" pattern works whenever the elements are organized into lexicographic groups of known size. It applies to permutations, combinations, paths on grids, and binary strings with a fixed number of 1's.

Edge cases

Before submitting, check these:

• k = 1: The first path is always all H's followed by all V's. Every comb check succeeds, so you always pick H until col reaches 0, then V for the rest.
• k = C(row + col, col): The last path is all V's followed by all H's. Every comb check fails, so you always skip to V first.
• row = 0: The only path is all H's. The loop appends H exactly col times.
• col = 0: The only path is all V's. The col > 0 check fails every time, so you always append V.
• Large grids: row and col can each be up to 15, giving paths of length 30. The total number of paths C(30, 15) is about 155 million, but the algorithm only runs 30 iterations regardless.

From understanding to recall

You understand the counting-and-skipping strategy. You can trace through an example and see how each binomial coefficient decides the next character. But can you write this solution from scratch in under two minutes?

That is what interviews demand. Under pressure, small details trip people up: using the wrong arguments to comb, forgetting to subtract the count from k when picking V, or mixing up row and col in the formula. These are not conceptual gaps. They are recall problems.

Spaced repetition fixes recall. You practice writing the combination count and the greedy loop from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "kth lexicographic path" and the code flows out without hesitation.

The combinatorial counting pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Unique Paths - The foundation for grid path counting. Once you know that C(m+n-2, n-1) counts all paths in a grid, the counting step in this problem is a direct application.
• Permutation Sequence - The same "kth element by counting and skipping" strategy, applied to permutations using factorials instead of binomial coefficients.
• Combinations - Generates all combinations using backtracking. Understanding how combinations are structured helps you see why comb(n, k) counts the right thing.

CodeBricks breaks Kth Smallest Instructions into its binomial path counting and greedy lexicographic construction building blocks, then drills them independently with spaced repetition. You type each brick from scratch until it is automatic. When the problem shows up in your interview, you do not think about it. You just write it.