Longest Increasing Path in Matrix

HardDynamic ProgrammingDepth-First SearchMatrixMemoization
Category: 2-D Dynamic Programming
Companies that ask this question:
AmazonGoogleFacebookMicrosoft

Approach

Longest Increasing Path in a Matrix

Problem Statement

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

From each cell, you can either move in 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]. Moving diagonally is not allowed.

Example 3:

Input: matrix = [[1]]

Output: 1

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • 0 <= matrix[i][j] <= 2^31 - 1

Approach

This problem can be solved using DFS with Memoization or Topological Sort.

Approach 1: DFS with Memoization

Intuition

The key insight is that for each cell, we can compute the longest increasing path starting from that cell. However, doing a naive DFS from every cell would result in O(2^(m*n)) time complexity due to overlapping subproblems.

By using memoization, we can cache the result for each cell and avoid recomputation, reducing the time complexity to O(m * n).

Algorithm Steps

  1. Initialize a memoization table memo[i][j] to store the longest path starting from cell (i, j)
  2. For each cell in the matrix:
    • Perform DFS to find the longest increasing path starting from that cell
    • Before computing, check if the result is already memoized
  3. In the DFS function:
    • If memoized, return the cached value
    • Otherwise, explore all four directions
    • For each valid neighbor with a greater value, recursively compute its longest path
    • Store the maximum path length in memo and return it
  4. Return the maximum path length across all starting cells

Recurrence Relation

dfs(i, j) = 1 + max(dfs(ni, nj)) for all valid neighbors (ni, nj)
            where matrix[ni][nj] > matrix[i][j]

Base case: dfs(i, j) = 1 (single cell path)

Approach 2: Topological Sort (BFS)

Intuition

We can think of the matrix as a directed acyclic graph (DAG) where there's an edge from cell A to cell B if B's value is greater than A's value and B is adjacent to A.

The longest path in a DAG can be found using topological sort:

  1. Calculate the outdegree of each cell (number of neighbors with greater values)
  2. Start BFS from all "leaf" cells (outdegree = 0)
  3. Process level by level, decreasing the outdegree of incoming edges
  4. The number of levels is the longest path length

Complexity Analysis

DFS with Memoization

  • Time Complexity: O(m × n)

    • Each cell is computed at most once
    • Each computation takes O(1) time (4 direction checks)

  • Space Complexity: O(m × n)

    • Memoization table: O(m × n)
    • Recursion stack: O(m × n) in worst case

Topological Sort

  • Time Complexity: O(m × n)

    • Computing outdegrees: O(m × n)
    • BFS traversal: O(m × n)

  • Space Complexity: O(m × n)

    • Outdegree table: O(m × n)
    • Queue: O(m × n) in worst case

Key Insights

  1. Memoization is Essential: Without memoization, the naive DFS would have exponential time complexity
  2. DAG Property: The "increasing" constraint ensures no cycles, making the graph a DAG
  3. Optimal Substructure: The longest path from a cell depends on the longest paths from its neighbors
  4. Direction Independence: We can explore neighbors in any order since we take the maximum

Common Pitfalls

  1. Forgetting Memoization: Results in TLE (Time Limit Exceeded)
  2. Incorrect Base Case: Should be 1 (single cell), not 0
  3. Boundary Checks: Must validate array bounds before accessing neighbors
  4. Strict Inequality: Path must be strictly increasing (not non-decreasing)

Edge Cases

  • Single cell matrix: Return 1
  • All cells have same value: Return 1 (no increasing path possible)
  • Matrix with all increasing values: Path length equals total cells

Related Problems

  • Longest Increasing Subsequence (LeetCode 300)
  • Number of Increasing Paths in Grid (LeetCode 2328)
  • Minimum Path Sum (LeetCode 64)
  • Unique Paths (LeetCode 62)

Tags

  • Dynamic Programming
  • Depth-First Search
  • Graph
  • Memoization
  • Topological Sort
  • Matrix
  • Hard

Solution

java
1class Solution {
2    // Approach 1: DFS with Memoization
3    // Time: O(m * n), Space: O(m * n)
4    public int longestIncreasingPath(int[][] matrix) {
5        if (matrix == null || matrix.length == 0) {
6            return 0;
7        }
8
9        int m = matrix.length;
10        int n = matrix[0].length;
11        int[][] memo = new int[m][n];
12        int maxPath = 0;
13
14        for (int i = 0; i < m; i++) {
15            for (int j = 0; j < n; j++) {
16                maxPath = Math.max(maxPath, dfs(matrix, i, j, memo));
17            }
18        }
19
20        return maxPath;
21    }
22
23    private int dfs(int[][] matrix, int row, int col, int[][] memo) {
24        // Return memoized result if available
25        if (memo[row][col] != 0) {
26            return memo[row][col];
27        }
28
29        int m = matrix.length;
30        int n = matrix[0].length;
31        int maxLength = 1; // Base case: single cell path
32
33        // Explore all four directions
34        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
35
36        for (int[] dir : directions) {
37            int newRow = row + dir[0];
38            int newCol = col + dir[1];
39
40            // Check bounds and increasing condition
41            if (newRow >= 0 && newRow < m &&
42                newCol >= 0 && newCol < n &&
43                matrix[newRow][newCol] > matrix[row][col]) {
44
45                int length = 1 + dfs(matrix, newRow, newCol, memo);
46                maxLength = Math.max(maxLength, length);
47            }
48        }
49
50        // Memoize and return result
51        memo[row][col] = maxLength;
52        return maxLength;
53    }
54
55    // Approach 2: Topological Sort (BFS)
56    // Time: O(m * n), Space: O(m * n)
57    public int longestIncreasingPathTopological(int[][] matrix) {
58        if (matrix == null || matrix.length == 0) {
59            return 0;
60        }
61
62        int m = matrix.length;
63        int n = matrix[0].length;
64        int[][] outdegree = new int[m][n];
65        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
66
67        // Calculate outdegree for each cell
68        for (int i = 0; i < m; i++) {
69            for (int j = 0; j < n; j++) {
70                for (int[] dir : directions) {
71                    int ni = i + dir[0];
72                    int nj = j + dir[1];
73                    if (ni >= 0 && ni < m && nj >= 0 && nj < n &&
74                        matrix[ni][nj] > matrix[i][j]) {
75                        outdegree[i][j]++;
76                    }
77                }
78            }
79        }
80
81        // Start BFS from leaves (outdegree == 0)
82        java.util.Queue<int[]> queue = new java.util.LinkedList<>();
83        for (int i = 0; i < m; i++) {
84            for (int j = 0; j < n; j++) {
85                if (outdegree[i][j] == 0) {
86                    queue.offer(new int[]{i, j});
87                }
88            }
89        }
90
91        int length = 0;
92        while (!queue.isEmpty()) {
93            int size = queue.size();
94            length++;
95            for (int k = 0; k < size; k++) {
96                int[] cell = queue.poll();
97                int i = cell[0];
98                int j = cell[1];
99
100                for (int[] dir : directions) {
101                    int ni = i + dir[0];
102                    int nj = j + dir[1];
103                    if (ni >= 0 && ni < m && nj >= 0 && nj < n &&
104                        matrix[ni][nj] < matrix[i][j]) {
105                        outdegree[ni][nj]--;
106                        if (outdegree[ni][nj] == 0) {
107                            queue.offer(new int[]{ni, nj});
108                        }
109                    }
110                }
111            }
112        }
113
114        return length;
115    }
116}
117
Loading visualizer...