Kth Smallest Instructions


Problem

Bob is standing at cell (0,0)(0, 0), and he wants to reach destination: (row,column)(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:

  • HH, meaning move horizontally (go right), or
  • VV, meaning move vertically (go down). Multiple instructions will lead Bob to destination. For example, if destination is (2,3)(2, 3), both HHHVVHHHVV and HVHVHHVHVH are valid instructions.

However, Bob is very picky. Bob has a lucky number kk, and he wants the kthk^{th} lexicographically smallest instructions that will lead him to destination. kk is 1-indexed.

Given an integer array destinationdestination and an integer kk, return the kthk^{th} lexicographically smallest instructions that will take Bob to destination.

Example

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 = 3
Output: "HHVVH"

Constraints

  • destination.length=2destination.length = 2
  • 1row,column151 \leq row, column \leq 15
  • 1knCr(row+column,row)1 \leq k \leq nCr(row + column, row), where nCr(a,b)nCr(a, b) denotes a choose b

Submit your solution at here

Solution

Intuition

I solve this in 2 steps:

  • Count possible ways to reach all i,j(i<n,j<m)i,j (i<n, j<m)
  • Travel from (0,0)(0,0), in each step, greedily decide if we should go right or down
    • If we go right, our rank stay the same, since HH is the best choice lexicography
    • If we go left, our rank decrease, we choose VV which essentially go down lexicography. Use precalculated array from previous step to determine how many rank do we go down
    • When we reach (n,m)(n,m), answer is the path made from the traversal

Code

class Solution {
public:
    string kthSmallestPath(vector<int>& destination, int k) {
        int n = destination[1]+1;
        int m = destination[0]+1;
        vector<vector<int>> f(n, vector<int>(m,0));
        f[0][0] = 1;
        for(int i = 0;i<n;i++) {
            f[i][0] = 1;
        }
        for(int i = 0;i<m;i++) {
            f[0][i] = 1;
        }
        for(int i = 1;i<n;i++) {
            for(int j = 1;j<m;j++) {
                f[i][j] = f[i-1][j] + f[i][j-1];
            }
        }
        string ret = "";
        int i = 0;
        int j = 0;
        int rank = 1;
        while(i<n && j<m) {
            int dx = n-1-i;
            int dy = m-1-j;
            if(dx == 0 && dy == 0) {
                break;
            }
            if(dx == 0) {
                j++;
                ret += "V";
            } else if(dy == 0) {
                i++;
                ret += "H";
            } else {
                int deltaV = f[dx][dy] - f[dx][dy-1];
                // if we go down, we go down deltaV in rank
                // if we go right, our rank stay the same
                if(rank + deltaV <= k) {
                    rank += deltaV;
                    j++;
                    ret += "V";
                } else {
                    i++;
                    ret += "H";
                }
            }
        }
        return ret;
        cout<<"f: "<<endl;
        for(int i = 0;i<n;i++) {
            for(int j = 0;j<m;j++) {
                cout<<f[i][j]<<' ';
            }
            cout<<endl;
        }
        cout<<endl;
        return ret;
    }
};