Simple DFS | Math | Intuition Explained | Python3 Code
Intuition\nWe keep two pointers(l, r) to determine the range of lexicographical orders possible. We update the range as we move. If we move right we eliminate (
# Intuition\nWe keep two pointers(l, r) to determine the range of lexicographical orders possible. We update the range as we move. If we move right we eliminate (from the range) all the lexicographical ways possible if we moved down and vice versa.\n\n## Step goes as:\n1. Initially l = 1, r = comb(rows+cols, rows) (total possible ways).\nEx: destination = [2, 3], total ways = comb(2+3, 2) = 10\n\n2. We determine the possible ways of moving right and down. We use nCr formula for that.\n    \n    1. right: n = row+(col-1), r = (col-1) or row (both works in combination)\n    \n    2. down: n = (row-1)+col, r = (row-1) or col\n\n3. If we go right -> l, r - down\n\n4. if we go down -> l - right, r\n\n5. When we move down in last column, right = 0. \n\n6. When we move right in last row, down = 0\n\n# Approach\nDFS and Combinatorics\n\n# Complexity\n- Time complexity: O(rows+cols)\n\n- Space complexity: O(rows+cols)\n\n# Code\n```python3 []\nclass Solution:\n    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n        rows, cols = destination\n        res: list[str] = list()\n\n        def dfs(l: int, r: int, row: int, col: int) -> bool:\n            if k < l or r < k: return False\n            if row == col == 0: return True\n            \n            right, down = 0, 0\n            if col: right = comb(row+col-1, row)\n            if row: down = comb(row+col-1, col)\n            \n            res.append("H")\n            if dfs(l, r-down, row, col-1):\n                return True\n\n            res[-1] = "V"\n            dfs(l-right, r, row-1, col)\n            return True\n\n        dfs(1, comb(rows+cols, rows), rows, cols)\n        return "".join(res)\n```
['Math', 'Combinatorics', 'Python', 'Python3']