LeetCode - Weekly Contest 213 - Kth Smallest Instructions

Question

Hi I participated in Leetcode weekly contest 213 and am facing issue with submission for below question Kth Smallest Instructions

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

'H', meaning move horizontally (go right), or 'V', meaning move vertically (go down). Multiple instructions will lead Bob to destination. For example, if destination is (2, 3), both "HHHVV" and "HVHVH" are valid instructions.

However, Bob is very picky. Bob has a lucky number k, and he wants the kth lexicographically smallest instructions that will lead him to destination. k is 1-indexed.

Given an integer array destination and an integer k, return the kth lexicographically smallest instructions that will take Bob to destination.

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"].

Constraints:
destination.length == 2
1 <= row, column <= 15
1 <= k <= nCr(row + column, row), where nCr(a, b) denotes a choose b.

I tried to create all the possible paths lexicographically and stop when count reached k, but it giving me TLE.

Below is my code :

public class Solution {
    String res = string.Empty;
    int count = 0;
    int K;
    public string KthSmallestPath(int[] destination, int k) {
        K=k;
        this.FindAllPaths("", destination[1], destination[0]);
        
        return res;
    }
    
    public void FindAllPaths(string currPath, int hRem, int vRem)
    {
        if(count == K)   return;
        if(hRem == 0 && vRem == 0)
        {
            res = currPath;
            count++;
            return;
        }
        
        if(hRem != 0)
        {
            this.FindAllPaths(currPath + 'H', hRem - 1, vRem);
        }
        
        if(vRem != 0)
        {
            this.FindAllPaths(currPath + 'V', hRem, vRem - 1);
        }
    }
}

Any idea on how can I optimize the code so that it passes all the test cases.

Answer 1

A review of your current code

class Solution uses the fields

String res = string.Empty;
int count = 0;
int K;

to pass information around between the “main” KthSmallestPath() function and the FindAllPaths() helper function. That makes the logic difficult to understand. Even worse, it causes wrong results if the function is called more than once:

String res1 = sol.KthSmallestPath(new int [] { 2, 3 }, 5);
// HVHVH (correct)
String res2 = sol.KthSmallestPath(new int [] { 2, 3 }, 1);
// VVHHH (wrong)

Try to pass all information as function arguments. If that is not possible, make sure to reset all the commonly used fields at the start of the function.

The horizontal and vertical spacing is not consistent: There should be spaces around the operator in

K=k;

and I suggest to always use curly braces with if-statements, e.g. here:

if(count == K)   return;

Finally, I had to think twice about the element of the given destination array correspond to rows/columns and to horizontal/vertical steps. Assinging these values to local variables with an explaining comment can make this more clear:

int vRem = destination[0]; // destination row = # of vertical steps 
int hRem = destination[1]; // destination column = # of horizontal steps

A better approach

In the “worst case”

String res = sol.KthSmallestPath(new int [] { 15, 15 }, 155117520);

your code builds recursively \$ \binom{30}{15} = 155117520\$ strings. This is a case where the “brute force” method simply does not work, and one has to find something more efficient.

In fact it is possible to find the k-th smallest permutation of a string with N characters in O(N) time and with O(N) memory, see for example

• Finding the n-th lexicographic permutation of a string on Mathematics Stack Exchange,
• Find n-th lexicographically permutation of a string | Set 2 on GeeksforGeeks.

The idea is to compute at every step how many permutations start with an H and how many start with a V and then choose the next letter accordingly.

As an example, compute the 5-th permutation of HHHVV.

• There are \$ \binom{5}{2} = 10 \$ permutations, and \$ \binom{4}{2} = 6 \$ start with H. Since \$ 5 \le 6 \$ the first letter must be H, and it remains to compute the 5-th permutation of HHVV.

• Next, there are \$ \binom{4}{2} = 6 \$ permutations of HHVV, and \$ \binom{3}{2} = 3 \$ start with H. Since \$ 5 > 3 \$ the next letter must be V, and it remains to compute the second permutation of HHV.

• This process is repeated until no Hs are left, and the remaining positions are filled with V.

Here is a possible implementation, using a recursive helper function:

public class Solution {

    // From https://rosettacode.org/wiki/Evaluate_binomial_coefficients#C.23
    static int binomial(int n, int k)
    {
        if (k > n - k)
        {
            k = n - k;
        }

        int c = 1;
        for (int i = 0; i < k; i++)
        {
            c = c * (n - i);
            c = c / (i + 1);
        }
        return c;
    }

    /*
     * Returns the `k`-th permutation of a string with `numH` 'H's and
     * `numV` 'V's in lexicographic order.
     */
    static string KthPermutation(int numH, int numV, int k)
    {
        if (numH == 0)
        {
            return new String('V', numV);
        }
        else
        {
            // Number of permutations starting with 'H':
            int c = binomial(numH + numV - 1, numV);
            if (k <= c)
            {
                return 'H' + KthPermutation(numH - 1, numV, k);
            }
            else
            {
                return 'V' + KthPermutation(numH, numV - 1, k - c);
            }
        }
    }

    public string KthSmallestPath(int[] destination, int k)
    {
        int numV = destination[0]; // destination row = # of vertical steps 
        int numH = destination[1]; // destination column = # of horizontal steps
        return KthPermutation(numH, numV, k);
    }
}

It computes

String res = sol.KthSmallestPath(new int [] { 15, 15 }, 155117520);

in 0.6 milliseconds on my MacBook (using Mono).