LeetCode 329: Longest Increasing Path in a Matrix Solution

Master LeetCode problem 329 (Longest Increasing Path in a Matrix), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

329. Longest Increasing Path in a Matrix

Hard

Array Dynamic Programming Depth-First Search Breadth-First Search Graph Topological Sort Memoization Matrix

Problem Explanation

Explanation

To solve this problem, we can use a dynamic programming approach along with depth-first search (DFS) to find the longest increasing path in the matrix starting from each cell. We will store the length of the longest increasing path starting at each cell in a separate 2D array. We will then iterate through each cell in the matrix and perform a DFS from that cell to find the longest increasing path.

Algorithm:

Initialize a 2D array dp to store the length of the longest increasing path starting from each cell.
Initialize a variable maxPath to store the maximum path length found so far.
Iterate through each cell in the matrix and perform DFS from that cell to find the longest increasing path.
During the DFS, for each neighboring cell that has a greater value, recursively call the DFS from that cell and update the length of the path.
Keep track of the maximum path length found during the DFS.
Return the maximum path length as the result.

Time Complexity: O(mn) where m is the number of rows and n is the number of columns in the matrix. Space Complexity: O(mn) for the dp array.

Solution Code

class Solution {
    int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int maxPath = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxPath = Math.max(maxPath, dfs(matrix, dp, i, j));
            }
        }
        
        return maxPath;
    }
    
    private int dfs(int[][] matrix, int[][] dp, int i, int j) {
        if (dp[i][j] != 0) {
            return dp[i][j];
        }
        
        int maxPath = 1;
        for (int[] dir : dirs) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length && matrix[x][y] > matrix[i][j]) {
                maxPath = Math.max(maxPath, 1 + dfs(matrix, dp, x, y));
            }
        }
        
        dp[i][j] = maxPath;
        return maxPath;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 329 (Longest Increasing Path in a Matrix)?

This page provides optimized solutions for LeetCode problem 329 (Longest Increasing Path in a Matrix) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 329 (Longest Increasing Path in a Matrix)?

The time complexity for LeetCode 329 (Longest Increasing Path in a Matrix) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 329 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 329 in Java, C++, or Python.

Back to LeetCode Solutions