Kth Smallest Instructions - Leetcode Solution

Problem Description:

The problem "Kth Smallest Instructions" on leetcode can be stated as follows:

Bob is standing at the bottom of an n x m grid. He wants to reach the top-right corner of the grid, and can only move in two directions: right and up. Bob's instruction is a string of length n+m containing 'H' or 'V', indicating that Bob should move horizontally or vertically respectively. The H's come first in the string, and all instructions must be used. Find the lexicographically k-th smallest such string of instructions that will get Bob to the top-right corner of the grid.

Solution approach:

We can start solving this problem in a brute-force manner, that is, by generating all possible valid paths that Bob could take from the bottom-left corner to the top-right corner of the grid and sort them lexicographically. We can then return the kth smallest such path. However, as the constraints can be as high as n, m, and k <= 12, we will definitely face time complexity issues with this approach.

Alternatively, an optimal approach to this problem would utilize the fundamental principles of combinatorics, specifically the binomial coefficient.

As we need to reach the top-right corner by making n+m moves, out of which n need to be H and m need to be V moves, the total number of unique strings of length n+m consisting of n H's and m V's is denoted by (n+m)C(n).

Hence, we can consider the number of paths that start with an H or V at the first step. If we assume it to be H, then the total number of valid paths that can be generated with n-1 H's and m V's is (n+m-1) C (n-1). Similarly, if we assume it to be V, then the total number of valid paths that can be generated with n H's and m-1 V's is (n+m-1) C (n).

We can start count these paths as we keep adding H or V directions to the resulting instruction string. Once we have counted k number of valid paths, we return the corresponding instruction string.

Pseudo-code for the solution:

Below is the pseudo-code for the above-discussed approach:

function kthSmallestPath(n, m, k): count_H = count_V = 0 result = "" while count_H < n and count_V < m: num_paths = choose(n+m-count_H-count_V-2, n-count_H) if num_paths >= k: result += 'H' count_H += 1 else: result += 'V' count_V += 1 k -= num_paths if count_H < n: result += 'H' * (n-count_H) else: result += 'V' * (m-count_V) return result

The function "choose(n, k)" is used to calculate the binomial coefficient. The function can be implemented as follows:

function choose(n, k): res = 1 for i from 1 to k: res *= (n-i+1)/i return res

Time complexity:

The time complexity of our optimal solution is O(n+m), where n and m are the dimensions of the given grid.

This solution uses combinatorics to count the number of possible paths, which can be done in O(1) time, and hence the overall time complexity of the solution is O(n+m).

Space complexity:

The space complexity of our solution is O(n+m), where n and m are the dimensions of the given grid. This is because we are using a string of length n+m to store the instruction string.

1