Problem Description

Given a grid with row rows and column columns, you start at the top-left cell (0, 0) and want to reach the bottom-right cell (row-1, column-1). You may only move down or right at each step. A move down is represented by the letter 'V' (for vertical), and a move right by 'H' (for horizontal).

You're given an integer k. Your task is to return the k-th lexicographically smallest sequence of instructions that will take you from the top-left to the bottom-right corner of the grid. Each instruction sequence is a string of length row + column - 2 consisting of exactly row - 1 'V's and column - 1 'H's.

Constraints:

• There is exactly one valid path for each unique arrangement of 'H' and 'V' moves.
• Each move can only be used the number of times allowed by the grid size (no re-use).
• 1 ≤ row, column ≤ 15
• 1 ≤ k ≤ C(row + column - 2, row - 1)

Thought Process

The brute-force way to solve this problem would be to generate all possible instruction sequences (permutations of 'H' and 'V'), sort them, and pick the k-th smallest one. However, this is inefficient because the number of possible sequences grows rapidly with the grid size (it's the binomial coefficient C(row + column - 2, row - 1)).

Instead, we can think recursively. At each step, we can choose to move either right ('H') or down ('V'), as long as we do not exceed the allowed number of each move. The key insight is that the number of possible sequences with a certain number of 'H's and 'V's remaining can be calculated using combinations. This allows us to "skip" large blocks of sequences and directly construct the k-th sequence letter by letter, without generating all possible paths.

Solution Approach

We'll construct the k-th smallest instruction sequence step by step, always choosing between 'H' and 'V' based on how many sequences start with each possible move. Here's how:

1. At each position, if there are h 'H's and v 'V's left, the number of sequences starting with 'H' is C(h + v - 1, v).
2. If k is less than or equal to the number of sequences starting with 'H', we choose 'H' for this position and decrease h by one.
3. Otherwise, we choose 'V', subtract the number of 'H'-starting sequences from k, and decrease v by one.
4. Repeat this process until all moves are used up.

We use a helper function to compute combinations efficiently. This approach avoids generating all sequences and directly constructs the answer in O(row + column) steps.

Example Walkthrough

Input: row = 2, column = 3, k = 3
Total moves needed: 2 'H's and 1 'V' (since row - 1 = 1, column - 1 = 2).
All possible sequences (sorted):

• HHV
• HVH
• VHH

Step-by-step:

1. At start: h = 2, v = 1, k = 3
2. Number of sequences starting with 'H': C(2,1) = 2
3. k > 2, so first letter is 'V'. Subtract 2 from k: k = 1, v = 0, h = 2
4. Now only 'H's left, fill in: "VHH"

Time and Space Complexity

• Brute-force approach: O(N log N) time and O(N) space, where N is the number of possible sequences (can be up to C(row + column - 2, row - 1)), which is exponential for larger grids.
• Optimized approach: O(row + column) time and O(1) space (excluding the result string), since we only compute combinations and build the answer step by step.

The combination calculation is efficient since the numbers involved are small (maximum 28 choose 14 for a 15x15 grid).

Summary

This problem can be solved elegantly by leveraging combinatorics to count the number of possible sequences at each decision point. Instead of generating all possible paths, we use the binomial coefficient to decide whether to place an 'H' or 'V' at each step, efficiently constructing the k-th lexicographically smallest instruction. This approach is both fast and memory-efficient, and it demonstrates the power of mathematical reasoning in algorithm design.

Code Implementation

import math

class Solution:
    def kthSmallestPath(self, destination, k):
        row, col = destination
        v = row
        h = col
        res = []
        for _ in range(row + col):
            if h == 0:
                res.append('V')
                v -= 1
            elif v == 0:
                res.append('H')
                h -= 1
            else:
                comb = math.comb(h + v - 1, v)
                if k <= comb:
                    res.append('H')
                    h -= 1
                else:
                    res.append('V')
                    k -= comb
                    v -= 1
        return ''.join(res)
      

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    long long comb(int n, int k) {
        long long res = 1;
        for (int i = 1; i <= k; ++i) {
            res = res * (n - i + 1) / i;
        }
        return res;
    }
    string kthSmallestPath(vector<int>& destination, int k) {
        int v = destination[0], h = destination[1];
        string res = "";
        for (int i = 0; i < v + h; ++i) {
            if (h == 0) {
                res += 'V';
                v--;
            } else if (v == 0) {
                res += 'H';
                h--;
            } else {
                long long c = comb(h + v - 1, v);
                if (k <= c) {
                    res += 'H';
                    h--;
                } else {
                    res += 'V';
                    k -= c;
                    v--;
                }
            }
        }
        return res;
    }
};
      

class Solution {
    public String kthSmallestPath(int[] destination, int k) {
        int v = destination[0], h = destination[1];
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < v + h; ++i) {
            if (h == 0) {
                res.append('V');
                v--;
            } else if (v == 0) {
                res.append('H');
                h--;
            } else {
                long c = comb(h + v - 1, v);
                if (k <= c) {
                    res.append('H');
                    h--;
                } else {
                    res.append('V');
                    k -= c;
                    v--;
                }
            }
        }
        return res.toString();
    }
    private long comb(int n, int k) {
        long res = 1;
        for (int i = 1; i <= k; ++i) {
            res = res * (n - i + 1) / i;
        }
        return res;
    }
}
      

var kthSmallestPath = function(destination, k) {
    let v = destination[0], h = destination[1];
    let res = [];
    function comb(n, k) {
        let res = 1;
        for (let i = 1; i <= k; ++i) {
            res = res * (n - i + 1) / i;
        }
        return res;
    }
    for (let i = 0; i < v + h; ++i) {
        if (h === 0) {
            res.push('V');
            v--;
        } else if (v === 0) {
            res.push('H');
            h--;
        } else {
            let c = comb(h + v - 1, v);
            if (k <= c) {
                res.push('H');
                h--;
            } else {
                res.push('V');
                k -= c;
                v--;
            }
        }
    }
    return res.join('');
};