LeetCode - Weekly Contest 213 - Kth Smallest Instructions

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).