LeetCode 3288: Length of the Longest Increasing Path

Explanation

To solve this problem, we can use a dynamic programming approach with memoization. We will start by sorting the coordinates based on their values and then apply dynamic programming to find the longest increasing path that contains the target coordinate at index k. We will recursively explore all possible paths from each coordinate to its neighboring coordinates and memoize the results to avoid redundant calculations.

1. Sort the coordinates based on their values.
2. Initialize a memoization array to store the length of the longest increasing path starting from each coordinate.
3. Define a recursive function to explore all possible paths and update the memoization array.
4. Start the recursion from the target coordinate at index k.
5. Explore all neighboring coordinates that have greater values.
6. If the path length from a neighboring coordinate is not yet calculated, recursively calculate it.
7. Update the current coordinate's path length with the maximum path length found from its neighbors.
8. Return the maximum path length for the target coordinate.

Time Complexity: O(n^2), where n is the number of coordinates. Space Complexity: O(n) for memoization array.

class Solution {
    public int longestIncreasingPath(int[][] coordinates, int k) {
        int n = coordinates.length;
        int[][] sortedCoordinates = new int[n][2];
        for (int i = 0; i < n; i++) {
            sortedCoordinates[i] = coordinates[i];
        }
        Arrays.sort(sortedCoordinates, (a, b) -> a[0] - b[0]);
        int[] memo = new int[n];
        return dfs(coordinates, sortedCoordinates, k, memo);
    }
    
    private int dfs(int[][] coordinates, int[][] sortedCoordinates, int k, int[] memo) {
        if (memo[k] != 0) {
            return memo[k];
        }
        int result = 1;
        for (int i = k + 1; i < coordinates.length; i++) {
            if (coordinates[i][1] > coordinates[k][1]) {
                result = Math.max(result, 1 + dfs(coordinates, sortedCoordinates, i, memo));
            }
        }
        memo[k] = result;
        return result;
    }
}