Lexicographically Smallest Path to Destination with Combinatorial Approach
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem can be solved by iteratively choosing between horizontal (\'H\') and vertic
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem can be solved by iteratively choosing between horizontal (\'H\') and vertical (\'V\') moves based on the number of available paths. We aim to find the kth lexicographically smallest path from the starting cell to the destination.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialize variables for the total number of vertical (\'V\') and horizontal (\'H\') moves needed.\n2. Use a combinatorial function to calculate the number of ways to choose \'V\' moves from the total moves.\n3. Iterate through each position and decide whether to add \'H\' or \'V\' based on the calculated combinatorial coefficient.\n4. Adjust the remaining steps and update the result string accordingly.\n5. Return the final result string representing the kth lexicographically smallest path.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(N), where N is the sum of the number of vertical and horizontal moves. The time complexity is dominated by the combinatorial calculation.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(1), as we use a constant amount of space to store variables and the result string.\n\n# Code\n```\n/**\n * @param {number[]} destination\n * @param {number} k\n * @return {string}\n */\nlet kthSmallestPath = function (destination, k) {\n  const [V, H] = destination\n  const N = V + H\n  let s = \'\', n = N, v = V, h = H\n  while (s.length < N) {\n    let c = p(n - 1, v)\n    if (h > 0 && c >= k) {\n      s += \'H\'\n      h--\n      n--\n    } else {\n      s += \'V\'\n      k -= c\n      v--\n      n--\n    }\n  }\n  return s\n}\n\nfunction p(n, r) {\n  let base = 1\n  for (let i = r + 1; i <= n; i++) {\n    base *= i\n  }\n  for (let i = 1; i <= n - r; i++) {\n    base /= i\n  }\n  return base\n}\n```
['JavaScript']