Kth Smallest Instructions LeetCode solution in C++

1
class Solution {
2
 public:
3
  string kthSmallestPath(vector<int> &destination, int k) {
4
    int n = destination[0] + 1, m = destination[1] + 1;
5

6
    // this code is straight forward it calculate and stores no. ways to go to
7
    // destination from i,j
8
    vector<vector<int>> ways(n, vector<int>(m));
9

10
    for (int i = n - 1; i >= 0; i--) {
11
      for (int j = m - 1; j >= 0; j--) {
12
        if (i == n - 1 || j == m - 1) {
13
          ways[i][j] = 1;
14
          continue;
15
        }
16
        ways[i][j] = ways[i][j + 1] + ways[i + 1][j];
17
      }
18
    }
19

20
    // with the help of above table ans can be generated
21
    // suppose we are at (i, j)   we need to decide whether to go Horizontal or
22
    // Vertical
23

24
    string ans = "";
25

26
    int i = 0, j = 0;
27
    while (i < n - 1 && j < m - 1) {
28
      // if k is less than no of ways to go from selecting horizontal path
29
      if (k <= ways[i][j + 1]) {
30
        ans = ans + 'H';
31
        j++;
32
      }
33
      // else we chose vertical for greater k
34
      else {
35
        k = k - ways[i][j + 1];
36
        i++;
37
        ans = ans + 'V';
38
      }
39
    }
40
    while (j++ < m - 1) ans = ans + 'H';
41
    while (i++ < n - 1) ans = ans + 'V';
42

43
    return ans;
44
  }
45
};