[Python3] greedy
Algo \nGiven m H and n V to place, we check if it is possible to place H. If so, decrement n; otherwise decrement m. Since there are comb(m+n-1, n-1) instructio
Algo \nGiven `m` H and `n` V to place, we check if it is possible to place H. If so, decrement `n`; otherwise decrement `m`. Since there are `comb(m+n-1, n-1)` instructions starting with H, the condition to check for placing H is `comb(m+n-1, n-1) >= k`. \n\nImplementation \n```\nclass Solution:\n    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n        m, n = destination # m "V" & n "H" in total \n        ans = ""\n        while n: \n            kk = comb(m+n-1, n-1) # (m+n-1 choose n-1) instructions starting with "H"  \n            if kk >= k: \n                ans += "H"\n                n -= 1\n            else: \n                ans += "V"\n                m -= 1\n                k -= kk \n        return ans + m*"V"\n```\n\nAnalysis\nTime complexity `O(M*N + N^2)`\nSpace complexity `O(M+N)`
['Python3']