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.

Examples

Example 1

1
2
3
4

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

1
2

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

Example 3

1
2

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

Solution

Method 1 – Combinatorics + Greedy

Intuition

At each step, decide whether to use ‘H’ or ‘V’ by counting the number of possible instructions starting with ‘H’. If k is greater than that, use ‘V’ and decrease k accordingly.

Approach

  1. Precompute binomial coefficients for all possible values.
  2. For each position, if the number of instructions starting with ‘H’ is at least k, append ‘H’ and decrease the number of columns; otherwise, append ‘V’, decrease k, and decrease the number of rows.
  3. Repeat until all moves are used.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    string kthSmallestPath(vector<int>& destination, int k) {
        int row = destination[0], col = destination[1];
        vector<vector<int>> comb(row+col+1, vector<int>(col+1, 0));
        for (int i = 0; i <= row+col; ++i) {
            comb[i][0] = comb[i][i] = 1;
            for (int j = 1; j < i; ++j)
                comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
        }
        string res;
        for (int i = 0; i < row+col; ++i) {
            if (col > 0) {
                int cnt = comb[row+col-1-i][col-1];
                if (k <= cnt) {
                    res += 'H';
                    --col;
                } else {
                    res += 'V';
                    k -= cnt;
                    --row;
                }
            } else {
                res += 'V';
                --row;
            }
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func kthSmallestPath(destination []int, k int) string {
    row, col := destination[0], destination[1]
    comb := make([][]int, row+col+1)
    for i := range comb {
        comb[i] = make([]int, col+1)
        comb[i][0], comb[i][i] = 1, 1
        for j := 1; j < i; j++ {
            comb[i][j] = comb[i-1][j-1] + comb[i-1][j]
        }
    }
    res := make([]byte, 0, row+col)
    for i := 0; i < row+col; i++ {
        if col > 0 {
            cnt := comb[row+col-1-i][col-1]
            if k <= cnt {
                res = append(res, 'H')
                col--
            } else {
                res = append(res, 'V')
                k -= cnt
                row--
            }
        } else {
            res = append(res, 'V')
            row--
        }
    }
    return string(res)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public String kthSmallestPath(int[] destination, int k) {
        int row = destination[0], col = destination[1];
        int[][] comb = new int[row+col+1][col+1];
        for (int i = 0; i <= row+col; ++i) {
            comb[i][0] = comb[i][i] = 1;
            for (int j = 1; j < i; ++j)
                comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
        }
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < row+col; ++i) {
            if (col > 0) {
                int cnt = comb[row+col-1-i][col-1];
                if (k <= cnt) {
                    res.append('H');
                    --col;
                } else {
                    res.append('V');
                    k -= cnt;
                    --row;
                }
            } else {
                res.append('V');
                --row;
            }
        }
        return res.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    fun kthSmallestPath(destination: IntArray, k: Int): String {
        var row = destination[0]
        var col = destination[1]
        val comb = Array(row+col+1) { IntArray(col+1) }
        for (i in 0..row+col) {
            comb[i][0] = 1; comb[i][i] = 1
            for (j in 1 until i)
                comb[i][j] = comb[i-1][j-1] + comb[i-1][j]
        }
        val res = StringBuilder()
        for (i in 0 until row+col) {
            if (col > 0) {
                val cnt = comb[row+col-1-i][col-1]
                if (k <= cnt) {
                    res.append('H'); col--
                } else {
                    res.append('V'); k -= cnt; row--
                }
            } else {
                res.append('V'); row--
            }
        }
        return res.toString()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def kthSmallestPath(self, destination: list[int], k: int) -> str:
        from math import comb
        row, col = destination
        res = []
        for _ in range(row + col):
            if col > 0:
                cnt = comb(row + col - 1, col - 1)
                if k <= cnt:
                    res.append('H')
                    col -= 1
                else:
                    res.append('V')
                    k -= cnt
                    row -= 1
            else:
                res.append('V')
                row -= 1
        return ''.join(res)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

impl Solution {
    pub fn kth_smallest_path(destination: Vec<i32>, mut k: i32) -> String {
        let (mut row, mut col) = (destination[0], destination[1]);
        let mut res = String::new();
        for _ in 0..row+col {
            if col > 0 {
                let cnt = binom(row+col-1, col-1);
                if k <= cnt {
                    res.push('H');
                    col -= 1;
                } else {
                    res.push('V');
                    k -= cnt;
                    row -= 1;
                }
            } else {
                res.push('V');
                row -= 1;
            }
        }
        res
    }
}
fn binom(n: i32, k: i32) -> i32 {
    let mut res = 1;
    for i in 0..k {
        res = res * (n-i) / (i+1);
    }
    res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    kthSmallestPath(destination: number[], k: number): string {
        let row = destination[0], col = destination[1];
        function comb(n: number, k: number): number {
            let res = 1;
            for (let i = 0; i < k; ++i) res = res * (n-i) / (i+1);
            return res;
        }
        let res = '';
        for (let i = 0; i < row+col; ++i) {
            if (col > 0) {
                const cnt = comb(row+col-1-i, col-1);
                if (k <= cnt) {
                    res += 'H';
                    --col;
                } else {
                    res += 'V';
                    k -= cnt;
                    --row;
                }
            } else {
                res += 'V';
                --row;
            }
        }
        return res;
    }
}

Complexity

  • ⏰ Time complexity: O(row + col)
    • For each move, we compute a binomial coefficient and append a character, resulting in O(row + col) operations.
  • 🧺 Space complexity: O(row + col)
    • The result string has length row + col, and we use constant extra space for computation.