How someone clueless at math solved it.
If you want the best, most elegant solution, this isn\'t the post for you... Here is how my brain wandered into a solution.\n\nFirst I simplified the problem in
If you want the best, most elegant solution, this isn\'t the post for you... Here is how my brain wandered into a solution.\n\nFirst I simplified the problem into it core part. What it\'s really asking is: if you have 3 H\'s and 2 V\'s, what is the k\'th arrangement of them. As long as you go down twice and to the right 3 times, it doesn\'t matter what order you do it in. I just decided to call H\'s 1\'s and V\'s 0\'s because that made more sense to me for some reason.\n\nFor reference here are the 10 possible arrangement for a 2 by 3 grid:\n```\n11100\n11010\n11001\n10110\n10101\n10011\n01110\n01101\n01011\n00111\n```\n\nI didn\'t know where to start, so I figured I would just write a function that returned the count of orderings for a given number of ones and zeros. For example, f(ones=3, zeros=2) = 10.\n\nI reasoned the base case of that function was if there are only ones OR there are only zeros - in that case the answer is obviously 1. Then I figured the left more element could either by a 1 or a 0. So logically, the total count must be the sum of those two possiblities. if the left most element is 1, (3, 2) -> (2, 2). If the left most is a zero, (3, 2) -> (3, 1). After some testing, this logic seemed sound.\n\n```\n    function solve(ones, zeros) {\n        if (ones === 0 || zeros === 0) {\n            return 1;\n        }\n        return solve(ones - 1, zeros) + solve(ones, zeros - 1)\n    }\n```\n\nI didn\'t really know what to do from here but I vaguely had a sense that this logic was leading in the right direction. I noticed that if you assume the first digit is a one, you get solve(3 - 1, 2) = 6 possible options, which matches up with the actual numbers I wrote down. \n\nSo I knew that if k was <= solve(2, 2) = 6, the first digit must be a 1. Else it must be a zero. You can see this by looking at example arrangements. Okayyy... If we know the first digit is a 1, now what? Well it seems like we reduced the problem down to something simpler. Let say k = 3, now we just need to find the 3rd element for 2 0\'s and 2 1\'s since we already figured out the first element is a 1. Lets guess that the next element is also a 1. We get solve(1, 2) = 3, which is still <= 3. So we know the next digit is also a 1! Let\'s guess one again the next element is a 1. We get solve(0, 2) = 1. Oops 3 > 1 so the next must be a zero. Okay again. solve(0, 1) = 1 < 3. so the next element must be a zero. Okay now we have no more zeros left so the last digit must be a 1. Done!\n\nNow lets try for k = 8. solve(2, 2) = 6 < 8. This means the first digit must be a 0. There are only 4 possible solutions where the first digit is 0. So what we are now looking for is the 2nd (8 - 6) solution where the first digit is 0. Let try solve(2, 1) = 3. 3 <= 3 so this time we know the next digit is a 1... And we continue this logic until we are out of digits to add. \n\nNow we just convert 1\'s and 0\'s into H\'s and V\'s and we are done!\n\nI got a time limit exceeded because the solve() function was very slow. So memoization (DP) fixed that and it was solved efficiently. The time complexity was the same as computing the memoized solve() function which was O(nm). \n\nIf you look closely, the solve() function actually creates pascal\'s triangle which you might note is part of other\'s solutions. So this is the same solution as other\'s, just a different thought process.\n\nFinal code:\n\n```\nvar kthSmallestPath = function(destination, k) {\n    \n    const cache = {};\n    function solve(ones, zeros) {\n        if (ones === 0 || zeros === 0) {\n            return 1;\n        }\n        const key = `${ones},${zeros}`;\n        if (key in cache) {\n            return cache[key];\n        }\n        const result = solve(ones - 1, zeros) + solve(ones, zeros - 1)\n        cache[key] = result;\n        return result\n    }\n    \n    let zeros = destination[0]\n    let ones = destination[1]\n    const size = zeros + ones;\n    const digits = []\n    while (digits.length < size) {\n        if (ones === 0) {\n            zeros--;\n            digits.push(0)\n            continue;\n        } else if (zeros === 0) {\n            ones--;\n            digits.push(1)\n            continue;\n        } \n        \n        const res = solve(ones - 1, zeros);\n        if (res >= k) {\n            ones--\n            digits.push(1)\n        } else {\n            zeros--\n            digits.push(0)\n            k -= (res)\n        }\n    }\n    return digits\n        .map(n => n === 1 ? \'H\' : \'V\')\n        .join(\'\');\n};\n```\n\n
[]