Kth smallest instructions( Java )
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding the k-th lexicographically smallest path from the top-left
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding the k-th lexicographically smallest path from the top-left to the bottom-right corner of a grid, where the path can only move right (\'H\') or down (\'V\'). This can be efficiently determined using dynamic programming (DP) to precompute the number of paths to each cell.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDynamic Programming Setup:\n\nWe use a DP table dp where dp[i][j] represents the number of unique paths to reach cell (i, j) from (0, 0).\nInitialize dp[0][0] = 1 because there is exactly one way to be at the starting point.\nDP Transition:\n\nPopulate the DP table:\ndp[i][j] = dp[i-1][j] + dp[i][j-1] for all valid indices (i, j) to compute the number of paths from the top-left corner to each cell.\nPath Construction:\n\nStarting from the bottom-right corner (m-1, n-1), determine whether to append \'H\' (move horizontally) or \'V\' (move vertically) based on the number of paths that can be taken:\nIf k <= dp[vertical][horizontal-1], append \'H\' and move left.\nOtherwise, append \'V\' and move up, adjusting k by subtracting the number of paths that go left.\nEdge Cases:\n\nHandle cases where m == 1 or n == 1 separately since paths are trivially either all \'H\' or all \'V\'.\n\n# Complexity\n### Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n O(m * n)\n\nBuilding the DP table takes O(m * n) time.\nConstructing the path from the DP table takes O(m + n) time in the worst case.\n\n### Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m * n)\n\nSpace used by the DP table to store results for each cell in the grid.\n\n# Code\n```\nclass Solution {\n    public String kthSmallestPath(int[] d, int k) {\n        int m = d[0] + 1; // number of H\n        int n = d[1] + 1; // number of V\n        \n        int[][] dp = new int[m][n];\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (i == 0 || j == 0) {\n                    dp[i][j] = 1;\n                } else {\n                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];\n                }\n            }\n        }\n        \n        StringBuilder sb = new StringBuilder();\n        int horizontal = n - 1;\n        int vertical = m - 1;\n        \n        while (horizontal > 0 && vertical > 0) {\n            int totalPathsToLeft = dp[vertical][horizontal - 1];\n            \n            if (k <= totalPathsToLeft) {\n                sb.append(\'H\');\n                horizontal--;\n            } else {\n                sb.append(\'V\');\n                k -= totalPathsToLeft;\n                vertical--;\n            }\n        }\n        \n        while (horizontal > 0) {\n            sb.append(\'H\');\n            horizontal--;\n        }\n        \n        while (vertical > 0) {\n            sb.append(\'V\');\n            vertical--;\n        }\n        \n        return sb.toString();\n    }\n}\n\n```
['Dynamic Programming', 'Java']