Skip to content

1643. Kth Smallest Instructions 👍

  • Time: $O(\texttt{row}(\texttt{column} + \texttt{row}))$
  • Space: $O(\texttt{row}(\texttt{column} + \texttt{row}))$
 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
31
32
33
34
35
36
37
class Solution {
 public:
  string kthSmallestPath(vector<int>& destination, int k) {
    string ans;
    int v = destination[0];
    int h = destination[1];
    const int totalSteps = v + h;
    const vector<vector<int>> comb = getComb(totalSteps - 1, v);

    for (int i = 0; i < totalSteps; ++i) {
      // If 'H' is picked, we can reach ranks [1, availableRank].
      const int availableRank = comb[h + v - 1][v];
      if (availableRank >= k) {  // Should pick 'H'.
        ans += 'H';
        --h;
      } else {  // Should pick 'V'.
        k -= availableRank;
        ans += 'V';
        --v;
      }
    }

    return ans;
  }

 private:
  // C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
  vector<vector<int>> getComb(int n, int k) {
    vector<vector<int>> comb(n + 1, vector<int>(k + 1));
    for (int i = 0; i <= n; ++i)
      comb[i][0] = 1;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= k; ++j)
        comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
    return comb;
  }
};

 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
31
32
33
34
class Solution {
  public String kthSmallestPath(int[] destination, int k) {
    StringBuilder sb = new StringBuilder();
    int v = destination[0];
    int h = destination[1];
    final int totalSteps = v + h;
    final int[][] comb = getComb(totalSteps - 1, v);

    for (int i = 0; i < totalSteps; ++i) {
      // If 'H' is picked, we can reach ranks [1, availableRank].
      final int availableRank = comb[h + v - 1][v];
      if (availableRank >= k) { // Should pick 'H'.
        sb.append('H');
        --h;
      } else { // Should pick 'V'.
        k -= availableRank;
        sb.append('V');
        --v;
      }
    }

    return sb.toString();
  }

  private int[][] getComb(int n, int k) {
    int[][] comb = new int[n + 1][k + 1];
    for (int i = 0; i <= n; ++i)
      comb[i][0] = 1;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= k; ++j)
        comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
    return comb;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def kthSmallestPath(self, destination: list[int], k: int) -> str:
    ans = []
    v, h = destination

    for _ in range(h + v):
      # If pick 'H', then we're able to reack 1, 2, ..., availableRank.
      availableRank = math.comb(h + v - 1, v)
      if availableRank >= k:  # Should pick 'H'.
        ans.append('H')
        h -= 1
      else:  # Should pick 'V'.
        k -= availableRank
        ans.append('V')
        v -= 1

    return ''.join(ans)