Tech Blogs LLD SDE Playbook DSA

Longest Increasing Path in a Matrix

Hard Top 250
Associated Patterns
2D Dynamic Programming Graphs
Interviewed At (Company Tags)
GoogleAmazonMicrosoftMeta
External Reference View on LeetCode

Problem Description

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move to four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Examples

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] or [1, 2, 6, 9] (wait, 9 is not in this matrix, it is [1, 2, 6] which is 3). The longest is [3, 4, 5, 6].

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 ≤ m, n ≤ 200
  • 0 ≤ matrix[i][j] ≤ 2³¹ - 1

Memoized DFS: DAG Traversal

Since we must move to a cell with a strictly greater value, the graph of cells is a Directed Acyclic Graph (DAG). There can be no cycles because heights are strictly increasing.

We can run depth-first search (DFS) from each cell to find the longest path:

  • Let dp[r][c] store the length of the longest increasing path starting from cell (r, c).
  • From (r, c), we visit all 4 neighbors (nr, nc) that are inside the grid and satisfy matrix[nr][nc] > matrix[r][c].
  • The transition is: dp[r][c] = 1 + max(dfs(nr, nc)) for all valid neighbors.
  • If a cell (r, c) has already been computed (dp[r][c] > 0), we return its cached value immediately.

Solution: Memoized DFS

class Solution {
    private int[][] memo;
    private int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private int rows, cols;

    public int longestIncreasingPath(int[][] matrix) {
        rows = matrix.length;
        cols = matrix[0].length;
        memo = new int[rows][cols];

        int maxLen = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                maxLen = Math.max(maxLen, dfs(matrix, r, c));
            }
        }
        return maxLen;
    }

    private int dfs(int[][] matrix, int r, int c) {
        if (memo[r][c] > 0) return memo[r][c];

        int maxPath = 1;

        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] > matrix[r][c]) {
                maxPath = Math.max(maxPath, 1 + dfs(matrix, nr, nc));
            }
        }

        memo[r][c] = maxPath;
        return maxPath;
    }
}
class Solution:
    def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
        rows, cols = len(matrix), len(matrix[0])
        memo = [[0] * cols for _ in range(rows)]
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(r: int, c: int) -> int:
            if memo[r][c] > 0:
                return memo[r][c]

            max_path = 1
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    max_path = max(max_path, 1 + dfs(nr, nc))

            memo[r][c] = max_path
            return max_path

        return max(dfs(r, c) for r in range(rows) for c in range(cols))
#include <vector>
#include <algorithm>

class Solution {
    std::vector<std::vector<int>> memo;
    int rows, cols;
    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    int dfs(const std::vector<std::vector<int>>& matrix, int r, int c) {
        if (memo[r][c] > 0) return memo[r][c];

        int maxPath = 1;
        for (auto& d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] > matrix[r][c]) {
                maxPath = std::max(maxPath, 1 + dfs(matrix, nr, nc));
            }
        }

        return memo[r][c] = maxPath;
    }

public:
    int longestIncreasingPath(std::vector<std::vector<int>>& matrix) {
        rows = matrix.size();
        cols = matrix[0].size();
        memo.assign(rows, std::vector<int>(cols, 0));

        int maxLen = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                maxLen = std::max(maxLen, dfs(matrix, r, c));
            }
        }
        return maxLen;
    }
};

Complexity Analysis:

  • Time Complexity: O(M * N) where M is rows and N is columns. Each cell is computed exactly once due to the cache.
  • Space Complexity: O(M * N) for the memoization table and recursion stack.

← All Problems