329. Longest Increasing Path in a Matrix – Leetcode Solutions

Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3:

Input: matrix = [[1]]
Output: 1

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        # If the matrix is empty, return 0
        if not matrix or not matrix[0]:
            return 0
        
        # Dimensions of the matrix
        m, n = len(matrix), len(matrix[0])
        
        # Memoization table to store the longest increasing path starting from each cell
        memo = [[-1] * n for _ in range(m)]
        
        # Directions for moving in the matrix: up, down, left, right
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        # Helper function to perform DFS and find the longest increasing path from (i, j)
        def dfs(i, j):
            # If the value is already computed, return it
            if memo[i][j] != -1:
                return memo[i][j]
            
            # Initialize the path length to 1 (itself)
            max_path = 1
            
            # Explore all four directions
            for dx, dy in directions:
                x, y = i + dx, j + dy
                # Check if the neighboring cell is within bounds and has a greater value
                if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                    # Recursively find the longest path from the neighboring cell
                    max_path = max(max_path, 1 + dfs(x, y))
            
            # Store the result in the memoization table
            memo[i][j] = max_path
            return memo[i][j]
        
        # Compute the longest increasing path for each cell in the matrix
        longest_path = 0
        for i in range(m):
            for j in range(n):
                longest_path = max(longest_path, dfs(i, j))
        
        return longest_path

class Solution {
public:
    // Directions array to move up, down, left, right
    vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    // Memoization table to store the longest path from each cell
    vector<vector<int>> memo;

    // DFS function to find the longest increasing path starting from cell (i, j)
    int dfs(vector<vector<int>>& matrix, int i, int j) {
        // If the value is already computed, return the stored value
        if (memo[i][j] != -1) return memo[i][j];
        
        int maxLength = 1;  // The minimum path length is 1 (the cell itself)

        // Explore all four possible directions
        for (const auto& dir : directions) {
            int x = i + dir[0];
            int y = j + dir[1];
            
            // Check if the next cell (x, y) is within bounds and has a strictly larger value
            if (x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size() && matrix[x][y] > matrix[i][j]) {
                // Recursively find the longest path from (x, y)
                int length = 1 + dfs(matrix, x, y);
                maxLength = max(maxLength, length);  // Update the max length for the current cell
            }
        }
        
        // Store the computed length in memoization table
        memo[i][j] = maxLength;
        return maxLength;
    }

    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty()) return 0;
        
        int m = matrix.size();       // Number of rows
        int n = matrix[0].size();    // Number of columns
        memo = vector<vector<int>>(m, vector<int>(n, -1));  // Initialize memo table with -1
        
        int maxPathLength = 0;  // Store the global maximum path length

        // Explore each cell in the matrix
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // For each cell, compute the longest increasing path using DFS
                maxPathLength = max(maxPathLength, dfs(matrix, i, j));
            }
        }

        return maxPathLength;  // Return the length of the longest increasing path
    }
};

var longestIncreasingPath = function(matrix) {
    // If the matrix is empty, return 0 as there are no paths
    if (!matrix || matrix.length === 0) return 0;
    
    const rows = matrix.length; // Number of rows in the matrix
    const cols = matrix[0].length; // Number of columns in the matrix
    
    // Directions to move in the matrix: up, down, left, right
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    // Cache for storing the results of longest path from each cell
    const cache = Array.from({ length: rows }, () => Array(cols).fill(0));
    
    // Helper function to perform DFS (Depth First Search)
    const dfs = (row, col) => {
        // If the longest path from this cell has been already computed, return it
        if (cache[row][col] !== 0) return cache[row][col];
        
        let maxPath = 1; // At least the path length is 1 (the cell itself)
        
        // Explore all four directions
        for (const [dx, dy] of directions) {
            const newRow = row + dx;
            const newCol = col + dy;
            
            // Check if the new position is within bounds and its value is greater than the current cell
            if (
                newRow >= 0 && newRow < rows &&
                newCol >= 0 && newCol < cols &&
                matrix[newRow][newCol] > matrix[row][col]
            ) {
                // Recur and find the longest path from the neighboring cell
                const path = 1 + dfs(newRow, newCol);
                maxPath = Math.max(maxPath, path); // Update maxPath if we find a longer path
            }
        }
        
        // Cache the result for the current cell
        cache[row][col] = maxPath;
        return maxPath;
    };
    
    let longestPath = 0;
    
    // Perform DFS for each cell in the matrix
    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            longestPath = Math.max(longestPath, dfs(row, col)); // Update the global longest path
        }
    }
    
    return longestPath; // Return the length of the longest increasing path
};

class Solution {
    // Directions to move in the matrix: up, down, left, right
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int rows, cols;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0; // If the matrix is empty, there's no path
        }

        rows = matrix.length;
        cols = matrix[0].length;

        // Memoization array to store the length of the longest path starting from each cell
        int[][] memo = new int[rows][cols];
        int maxPathLength = 0; // This will store the result: the maximum path length

        // Loop through every cell in the matrix
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // Calculate the longest path starting from this cell and update the result
                maxPathLength = Math.max(maxPathLength, dfs(matrix, i, j, memo));
            }
        }

        return maxPathLength; // Return the maximum path length found
    }

    // Depth-first search (DFS) function to explore the longest increasing path starting from (row, col)
    private int dfs(int[][] matrix, int row, int col, int[][] memo) {
        // If the result for this cell has already been computed, return it
        if (memo[row][col] > 0) {
            return memo[row][col];
        }

        int maxPath = 1; // The minimum path length is 1 (the cell itself)

        // Explore all four directions (up, down, left, right)
        for (int[] direction : DIRECTIONS) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];

            // Check if the new position is within bounds and has a greater value
            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && matrix[newRow][newCol] > matrix[row][col]) {
                // Recursively calculate the path length from the new cell
                int pathLength = 1 + dfs(matrix, newRow, newCol, memo);
                maxPath = Math.max(maxPath, pathLength); // Update the maximum path length
            }
        }

        // Memoize the result for the current cell
        memo[row][col] = maxPath;
        return maxPath;
    }
}