ct fletcher
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nimport java.util.*;\n\n\nclass Solution {\n    // RIGHT before DOWN\n\n    // NOTICE: because of the Manhattan way of moving, path is always same len N !!!\n    // Moreover, path will ALWAYS have SAME number of RIGHTs and DOWNs\n    // num RIGHTs   = cols - 1 = colT\n    // num DOWNs    = rows - 1 = rowT\n    // len path = rowT + colT  = N\n\n    // sorted paths N = 5\n    // R,R,R,D,D\n    // R,R,D,R,D\n    // R,R,D,D,R\n    // ....\n\n    // 10 total combinations; choose 3 positions for RIGHT out of 5 possibilities\n    // C(5,3) = 5! / 3! * 2! = 4*5/2 = 10\n    // num paths = C(N,colT)\n\n    // IDEA 1: Brute force shift the string, like in the Iterator problem; O(generates all perms 1..K) = O(K!)\n    // IDEA 2: 2^N bit masks, loop over all with RIGHT cnt bits, those positions\n    // are the ones where we put R, they are lexicographically sorted  O(2^N)\n\n    // OPTIMIZE IDEA 1: by knowing when to skip generating specific sequences\n    // if we start with RIGHT, the number of paths are C(n - 1, colT - 1)\n    // compare that with the goal K !!!\n\n    // simulate the idea:\n    // sorted paths N = 5;  total seqs = 10 = C(5,3)\n    // R,...         seqs = C(4,2) = 6   seq ids 1...6\n    // R,R,..        seqs = C(3,1) = 3\n    // R,R,R,.       seqs = C(2,0) = 1    if K = 1 we go down to here and then add DDs\n    // R,R,D.        seqs = C(2,1) = 2    if K > 1 we get to here\n    \n    // k = 7\n    // D,...         adjusted K = 1;   if we put R now seqs = C(4,3) = 4\n    // D,R           C(3,2) = 3\n    // D,R,R         C(2,1) = 2\n    // D,R,R,R       C(2,0) = 1\n\n\n    // notice C(n,k) C(N-1,K-1) => PASCAL\'S TRIANGLE !!!\n    // C(N,K) = C(N-1,K-1) + C(N-1,K)\n\n    public String kthSmallestPath(int[] destination, int k) {\n        int rowT = destination[0];\n        int colT = destination[1];\n        int n = rowT + colT;\n        int rightsToPut = colT;\n        StringBuilder sb = new StringBuilder(n);\n        for (int i = 1; i <= n && rightsToPut > 0; i++) { // ith char\n            long putRCombs = nCk(n - i, rightsToPut - 1);\n//            long putDCombs = nCk(n - i, rightsToPut);\n            if (k <= putRCombs) {\n                sb.append(\'H\');\n                rightsToPut--;\n            } else {\n                k -= putRCombs; // skipped those combs\n                sb.append(\'V\');\n            }\n        }\n\n        while (sb.length() < n) sb.append(\'V\'); // add rest of DOWNs\n        return sb.toString();\n    }\n\n    long nCk(long n, long k) {\n        long cnt = 1;\n        for (int i = 0; i < k; i++) {\n            cnt *= n - i;\n            cnt /= i + 1;\n        }\n        return cnt;\n    }\n\n\n}\n\n```
['Java']