Introduction

In this blog post, we will explore how to solve the LeetCode problem "1643" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Bob is standing at cell (0, 0), and he wants to reach destination: (row, column). He can only travel right and down. You are going to help Bob by providing instructions for him to reach destination. The instructions are represented as a string, where each character is either: 'H', meaning move horizontally (go right), or 'V', meaning move vertically (go down). Multiple instructions will lead Bob to destination. For example, if destination is (2, 3), both "HHHVV" and "HVHVH" are valid instructions. However, Bob is very picky. Bob has a lucky number k, and he wants the kth lexicographically smallest instructions that will lead him to destination. k is 1-indexed. Given an integer array destination and an integer k, return the kth lexicographically smallest instructions that will take Bob to destination. Example 1: Input: destination = [2,3], k = 1 Output: "HHHVV" Explanation: All the instructions that reach (2, 3) in lexicographic order are as follows: ["HHHVV", "HHVHV", "HHVVH", "HVHHV", "HVHVH", "HVVHH", "VHHHV", "VHHVH", "VHVHH", "VVHHH"]. Example 2: Input: destination = [2,3], k = 2 Output: "HHVHV" Example 3: Input: destination = [2,3], k = 3 Output: "HHVVH" Constraints: destination.length == 2 1 <= row, column <= 15 1 <= k <= nCr(row + column, row), where nCr(a, b) denotes a choose b​​​​​.

Explanation

Here's a breakdown of the solution:

• Combinations and Lexicographical Order: The number of paths to reach (row, col) is nCr(row + col, row). We leverage this fact to determine which 'H' or 'V' should come next in the kth lexicographically smallest path.
• Iterative Path Construction: We iteratively build the path string. In each step, we check if adding an 'H' would result in a number of paths greater than or equal to k. If it does, we add 'H' to the path. Otherwise, we add 'V', and adjust k accordingly, reducing it by the number of paths that start with 'H'.

• Precompute Combinations: We precompute the combinations to optimize the calculation of the number of possible paths.

• Runtime & Storage Complexity: O(row + col), O((row + col) * (min(row, col) + 1)) respectively, due to the combination calculation and path construction.

Code

    class Solution:
    def kthSmallestPath(self, destination: list[int], k: int) -> str:
        row, col = destination
        n = row + col
        dp = [[0] * (col + 1) for _ in range(n + 1)]

        # Precompute combinations using dynamic programming
        for i in range(n + 1):
            dp[i][0] = 1
        for i in range(col + 1):
            dp[0][i] = 1
        for i in range(1, n + 1):
            for j in range(1, min(i, col) + 1):
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

        result = ""
        curr_row = 0
        curr_col = 0

        for _ in range(n):
            if col > 0:
                horizontal_paths = dp[row + col - 1][row]
                if k <= horizontal_paths:
                    result += "H"
                    col -= 1
                else:
                    result += "V"
                    row -= 1
                    k -= horizontal_paths
            else:
                result += "V"  # Only vertical moves remaining
                row -= 1

        return result