# Kth Smallest Instructions
**Difficulty:** HARD
[External](https://leetcode.com/problems/kth-smallest-instructions)
Canonical: https://scaleengineer.com/dsa/problems/kth-smallest-instructions
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
**Data structures:** Array
---
## Problem
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:**

![](https://assets.glich.co/dsa/kth-smallest-instructions/image0.png)

**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:**

**![](https://assets.glich.co/dsa/kth-smallest-instructions/image1.png)**

**Input:** destination = [2,3], k = 2
**Output:** "HHVHV"

**Example 3:**

**![](https://assets.glich.co/dsa/kth-smallest-instructions/image2.png)**

**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`​​​​​.

# Approaches
## Backtracking with Pruning
This approach involves generating all possible valid instruction strings in lexicographical order using a backtracking (or Depth First Search) algorithm. Since 'H' comes before 'V' lexicographically, we prioritize exploring paths by adding 'H' before 'V'. We maintain a counter `k`. When we find a valid path, we decrement the counter. The path that makes the counter zero is our answer. This avoids generating and storing all paths, but can still be slow if `k` is large.
**Time:** O(k * (row + column)). In the worst case, `k` can be as large as `C(row + column, row)`, making the complexity `O(C(row + column, row) * (row + column))`. This is too slow for the given constraints. · **Space:** O(row + column). The space is dominated by the recursion stack depth and the string builder used to construct the path, both of which are proportional to the length of the path.
**Pros:** Conceptually simple and easy to implement.; More memory-efficient than generating and storing all permutations at once.
**Cons:** The time complexity is prohibitive for the given constraints, as it may need to generate a large number of paths before finding the k-th one.; This approach will likely result in a 'Time Limit Exceeded' error for larger values of `row`, `column`, and `k`.
### Explanation
The algorithm uses a recursive function, say `generate(currentPath, h_rem, v_rem)`, where `h_rem` and `v_rem` are the remaining horizontal and vertical moves needed.

The base case for the recursion is when a full path is formed (`h_rem == 0` and `v_rem == 0`). In the base case, we decrement a global counter `k`. If `k` becomes 0, we've found our target path and store it.

In the recursive step, we first check if we can append 'H' (i.e., if `h_rem > 0`). If so, we append 'H' and make a recursive call with `h_rem - 1`. After this call returns, we backtrack by removing the added 'H'.

If the k-th path has not been found yet, we then check if we can append 'V' (i.e., if `v_rem > 0`). If so, we append 'V' and recurse with `v_rem - 1`, backtracking afterwards.

This process naturally generates paths in lexicographical order. We can stop the entire search process once the k-th path is found.

```java
class Solution {
    private int k;
    private String result = "";

    public String kthSmallestPath(int[] destination, int k) {
        this.k = k;
        int v = destination[0];
        int h = destination[1];
        generate(new StringBuilder(), h, v);
        return result;
    }

    private void generate(StringBuilder currentPath, int h, int v) {
        // If a path is already found, no need to continue.
        if (!result.isEmpty()) {
            return;
        }

        // Base case: a full path is formed.
        if (h == 0 && v == 0) {
            this.k--;
            if (this.k == 0) {
                result = currentPath.toString();
            }
            return;
        }

        // Recursive step: try 'H' first for lexicographical order.
        if (h > 0) {
            currentPath.append('H');
            generate(currentPath, h - 1, v);
            currentPath.deleteCharAt(currentPath.length() - 1);
        }
        
        if (!result.isEmpty()) {
            return;
        }

        // Then try 'V'.
        if (v > 0) {
            currentPath.append('V');
            generate(currentPath, h, v - 1);
            currentPath.deleteCharAt(currentPath.length() - 1);
        }
    }
}
```
### Algorithm
- The core idea is to generate all possible valid instruction strings in lexicographical order and stop when the k-th one is found.
- A recursive function (DFS) is used to build the path character by character.
- To ensure lexicographical order, the recursive function always tries to add an 'H' (horizontal move) before trying to add a 'V' (vertical move).
- A global counter, initialized to `k`, is decremented every time a complete valid path is generated.
- The recursion stops and the path is stored as the result when the counter reaches 0.
- To optimize, the search is pruned: if the result is found, all subsequent recursive calls terminate immediately.

## Combinatorial Construction
This is a highly efficient mathematical approach. Instead of generating paths, we construct the k-th path directly, character by character. At each step, we decide whether to place an 'H' or a 'V'. The decision is based on how many lexicographically smaller paths we would skip by choosing one character over the other.
**Time:** O((row + column) * column). The precomputation of the combinations table takes `O((row + column) * column)` time. The path construction loop runs `row + column` times with constant time operations inside. Given the constraints, this is very fast. · **Space:** O((row + column) * column). This space is used to store the precomputed combinations table. The space for the result string is O(row + column).
**Pros:** Extremely efficient and deterministic.; Directly constructs the result without any unnecessary exploration or backtracking.; Guaranteed to pass within time limits for the given constraints.
**Cons:** Requires understanding of combinatorics (binomial coefficients).; The logic is less direct than a simple search algorithm.
### Explanation
The total length of the path is `n = row + column`. We need to place `row` 'V's and `column` 'H's. We build the path of length `n` from left to right. At each position, we decide whether to put 'H' or 'V'.

Let's say we have `h` horizontal moves and `v` vertical moves remaining. We consider placing 'H' at the current position. If we do, the rest of the path will have `h-1` 'H's and `v` 'V's. The number of such paths is given by the binomial coefficient `C(h - 1 + v, h - 1)`.

Let this count be `combinations_with_H`. We compare `k` with `combinations_with_H`:
- If `k <= combinations_with_H`, it means our target path is within this group of paths that start with 'H' at this position. So, we append 'H' to our result, decrement `h`, and proceed to the next position.
- If `k > combinations_with_H`, our target path is not in this group. It must be in the group of paths that start with 'V'. We append 'V' to our result, decrement `v`, and update `k` by subtracting the number of paths we skipped: `k = k - combinations_with_H`.

We repeat this for all `n` positions. To efficiently calculate the combinations `C(n, k)`, we can precompute them using Pascal's identity and store them in a 2D array.

```java
class Solution {
    public String kthSmallestPath(int[] destination, int k) {
        int v = destination[0];
        int h = destination[1];
        int totalMoves = v + h;

        // Precompute combinations C(n, k)
        long[][] C = new long[totalMoves + 1][h + 1];
        for (int i = 0; i <= totalMoves; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i && j <= h; j++) {
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < totalMoves; i++) {
            if (h > 0) {
                // Number of paths starting with 'H'
                // Remaining moves: h-1 'H's, v 'V's. Total: h-1+v
                long combinationsWithH = C[h - 1 + v][h - 1];
                
                if (k <= combinationsWithH) {
                    sb.append('H');
                    h--;
                } else {
                    k -= combinationsWithH;
                    sb.append('V');
                    v--;
                }
            } else {
                // No more 'H's left, must be 'V'
                sb.append('V');
                v--;
            }
        }
        return sb.toString();
    }
}
```
### Algorithm
- First, precompute the binomial coefficients `C(n, k)` for `n` up to `row + column` and `k` up to `column`. This can be done using Pascal's identity: `C(n, k) = C(n-1, k-1) + C(n-1, k)`.
- Initialize `h = column` and `v = row` as the number of horizontal and vertical moves remaining.
- Iterate `row + column` times to build the instruction string character by character.
- In each iteration, decide whether to place an 'H' or a 'V'.
- If `h > 0`, calculate the number of paths that can be formed if we choose 'H' for the current position. This is `C(h - 1 + v, h - 1)`.
- If `k` is less than or equal to this number, it means the k-th path starts with 'H'. Append 'H' to the result and decrement `h`.
- Otherwise, the k-th path must start with 'V'. Append 'V' to the result, decrement `v`, and subtract the number of skipped 'H' paths from `k` (`k = k - C(h - 1 + v, h - 1)`).
- If `h` becomes 0 at any point, all remaining moves must be 'V'.

# Solutions
### Java

```java
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();
  }
}

```

### Python

```python
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)

```

### CPP

```cpp
class Solution {
public:
  string kthSmallestPath(vector<int> &destination, int k) {
    int v = destination[0], h = destination[1];
    int n = v + h;
    int c[n + 1][h + 1];
    memset(c, 0, sizeof(c));
    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];
      }
    }
    string ans;
    for (int i = 0; i < n; ++i) {
      if (h == 0) {
        ans.push_back('V');
      } else {
        int x = c[v + h - 1][h - 1];
        if (k > x) {
          ans.push_back('V');
          --v;
          k -= x;
        } else {
          ans.push_back('H');
          --h;
        }
      }
    }
    return ans;
  }
};

```