Code Implementation

class Solution:
    def longestIncreasingPath(self, matrix):
        if not matrix or not matrix[0]:
            return 0
        m, n = len(matrix), len(matrix[0])
        memo = [[0]*n for _ in range(m)]

        def dfs(x, y):
            if memo[x][y]:
                return memo[x][y]
            val = matrix[x][y]
            max_len = 1
            for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                nx, ny = x+dx, y+dy
                if 0<=nx<m and 0<=ny<n and matrix[nx][ny] > val:
                    max_len = max(max_len, 1 + dfs(nx, ny))
            memo[x][y] = max_len
            return max_len

        return max(dfs(i, j) for i in range(m) for j in range(n))
    

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> memo(m, vector<int>(n, 0));
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                res = max(res, dfs(matrix, memo, i, j));
            }
        }
        return res;
    }
private:
    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& memo, int x, int y) {
        if (memo[x][y]) return memo[x][y];
        int m = matrix.size(), n = matrix[0].size(), val = matrix[x][y], max_len = 1;
        vector<pair<int, int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for (auto d : dirs) {
            int nx = x + d.first, ny = y + d.second;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] > val) {
                max_len = max(max_len, 1 + dfs(matrix, memo, nx, ny));
            }
        }
        memo[x][y] = max_len;
        return max_len;
    }
};
    

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

var longestIncreasingPath = function(matrix) {
    if (!matrix || !matrix.length || !matrix[0].length) return 0;
    const m = matrix.length, n = matrix[0].length;
    const memo = Array.from({length: m}, () => Array(n).fill(0));
    
    const dfs = (x, y) => {
        if (memo[x][y]) return memo[x][y];
        let maxLen = 1;
        const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
        for (const [dx, dy] of dirs) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] > matrix[x][y]) {
                maxLen = Math.max(maxLen, 1 + dfs(nx, ny));
            }
        }
        memo[x][y] = maxLen;
        return maxLen;
    };
    
    let res = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            res = Math.max(res, dfs(i, j));
        }
    }
    return res;
};
    

Problem Description

Given a 2D integer matrix matrix, find the length of the longest increasing path in matrix. From each cell, you can move in four directions: up, down, left, or right. You may not move diagonally or move outside the boundary of the matrix. You cannot revisit the same cell within a single path. A path is considered increasing if each next cell has a strictly higher value than the previous one.

• Each cell can be used only once per path.
• The path may start and end at any cell in the matrix.
• Return the maximum length of such an increasing path.

Thought Process

At first glance, the problem resembles finding the longest path in a grid, with the restriction that each move must go to a strictly larger value. The brute-force approach would be to start a DFS from every cell, exploring all possible increasing paths, and tracking the maximum length found. However, this quickly becomes inefficient due to repeated exploration of the same subproblems from different starting points.

To optimize, we observe that the result of the longest increasing path starting from a particular cell only depends on the values of its neighbors and not on the path taken to reach the cell. This means we can cache or "memoize" the result for each cell, so that we do not recompute it if we encounter the cell again in a different DFS traversal.

This insight shifts our approach from brute-force to a dynamic programming solution with memoization, drastically improving performance.

Solution Approach

• Step 1: DFS Traversal
  • For each cell in the matrix, initiate a DFS to explore all increasing paths starting from that cell.
• Step 2: Memoization
  • Use a memoization table (memo) with the same dimensions as matrix to store the length of the longest increasing path starting from each cell.
  • If a cell's value has already been computed, return it immediately to avoid redundant calculations.
• Step 3: Valid Moves
  • From each cell, try moving up, down, left, and right, but only to neighbors with strictly greater values.
  • For each valid move, recursively call DFS and track the maximum path length found.
• Step 4: Aggregation
  • After processing all cells, the answer is the maximum value in the memoization table.
• Why Memoization?
  • Each cell's result is only computed once, reducing time complexity from exponential to linear in the number of cells.

Example Walkthrough

Consider the following matrix:

    [
      [9, 9, 4],
      [6, 6, 8],
      [2, 1, 1]
    ]
  

1. Start DFS from cell (2,0) with value 2. Its only increasing neighbor is (1,0) with value 6.
2. From (1,0), the only increasing neighbor is (0,0) with value 9.
3. (0,0) has no increasing neighbors, so its longest path is 1.
4. Backtrack: (1,0) path length = 1 + (0,0) = 2.
5. Backtrack: (2,0) path length = 1 + (1,0) = 3.
6. Repeat this process for all other cells, memoizing results.
7. The longest path found in the entire matrix is 4: (2,1) → (2,0) → (1,0) → (0,0).

Time and Space Complexity

• Brute-force:
  • Time: Exponential, as each cell could recursively explore all possible paths without memoization.
  • Space: O(mn) for the call stack in the worst case.
• Optimized (DFS + Memoization):
  • Time: O(mn), where m and n are the matrix dimensions. Each cell is computed once, and each DFS explores up to 4 neighbors.
  • Space: O(mn) for the memoization table and recursion stack.

Summary

The Longest Increasing Path in a Matrix problem is best solved with DFS and memoization. By caching the result of each subproblem, we avoid redundant computation and ensure each cell is visited only once. This transforms a potentially exponential brute-force approach into an efficient linear-time solution, making it both elegant and practical for large matrices.