[Kotlin] Finding Kth Lexicographically Smallest Path to Destination
Intuition\nTo reach the destination in lexicographically smallest instructions, we can follow the approach of generating combinations of \'H\' (right) and \'V\'
# Intuition\nTo reach the destination in lexicographically smallest instructions, we can follow the approach of generating combinations of \'H\' (right) and \'V\' (down) movements. We\'ll calculate the number of ways to reach each cell using dynamic programming (DP) to build a combination table. Then we\'ll construct the path by choosing the direction based on the number of ways to reach the next cell.\n\n# Approach\n1. Initialize `hCount` to the column count and `vCount` to the row count of the destination.\n2. Create a DP table `dp` of size `(row + col + 1) x (col + 1)` to store the combinations.\n3. Fill the DP table by calculating binomial coefficients.\n4. Use a StringBuilder `sb` to construct the path.\n5. Iterate `totalMoves` times (sum of row and column):\n   - If `hCount` is greater than 0:\n     - Calculate the combination `comb` using DP table.\n     - If `remainingK` is less than or equal to `comb`, append \'H\' to `sb` and decrement `hCount`.\n     - Otherwise, append \'V\' to `sb`, decrement `vCount`, and subtract `comb` from `remainingK`.\n   - If `hCount` is 0, append \'V\' to `sb` and decrement `vCount`.\n6. Return the path `sb.toString()`.\n\n# Complexity\n- Time complexity: O(row + col) to calculate DP table, O(row + col) to build the path.\n- Space complexity: O(row + col) for the DP table and StringBuilder.\n\n# Code\n```\nclass Solution {\n    fun kthSmallestPath(destination: IntArray, k: Int): String {\n        val (row, col) = destination\n        var hCount = col\n        var vCount = row\n        val totalMoves = row + col\n        val dp = Array(totalMoves + 1) { IntArray(col + 1) }\n\n        // Calculate binomial coefficients\n        for (i in 0..totalMoves) {\n            dp[i][0] = 1\n            for (j in 1..minOf(i, col)) {\n                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]\n            }\n        }\n\n        val sb = StringBuilder()\n\n        // Build the path\n        var remainingK = k\n        for (i in 0 until totalMoves) {\n            if (hCount > 0) {\n                val comb = dp[hCount + vCount - 1][hCount - 1]\n                if (remainingK <= comb) {\n                    sb.append(\'H\')\n                    hCount--\n                } else {\n                    sb.append(\'V\')\n                    vCount--\n                    remainingK -= comb\n                }\n            } else {\n                sb.append(\'V\')\n                vCount--\n            }\n        }\n\n        return sb.toString()\n    }\n}\n\n```
['Array', 'Math', 'Dynamic Programming', 'Combinatorics', 'Kotlin']