Longest Increasing Path in a Matrix

How it works

We can think of the matrix as a directed graph:

• each cell is a node
• we draw a directed edge from a smaller value to a larger value (only for 4-direction neighbors)

Because edges always go from smaller to larger, the graph has no cycles (values must strictly increase), so it is a DAG.

In a DAG, the longest path length can be found using topological order.
Kahn’s algorithm (BFS with indegrees) processes nodes level by level:

• nodes with indegree 0 are the “smallest” starting points (no smaller neighbor points into them)
• removing one layer may unlock the next larger layer

Each BFS layer corresponds to taking one step forward in an increasing path.
So, the number of layers processed is exactly the length of the longest increasing path.

Steps

1. Treat each cell (r, c) as a node.
2. Compute indegree[r][c]:
   • indegree[r][c] = number of neighboring cells with a smaller value (neighbors that point into (r, c))
   • For each cell, look at its 4 neighbors:
     • if a neighbor value is smaller, increase the cell's indegree
3. Initialize a queue with all cells that have indegree 0:
   • these are local minima and can start an increasing path
4. Perform BFS in layers:
   • for each layer:
     • pop all current nodes in the queue
     • for each popped cell, check its 4 neighbors
     • if a neighbor has a larger value, it is reachable from the current cell:
       • decrement that neighbor's indegree
       • if the neighbor's indegree becomes 0, push it into the queue
   • after finishing the layer, increment the answer (LIS += 1)
5. When the queue becomes empty, all nodes have been processed.
6. Return the number of layers processed (LIS), which equals the longest increasing path length.

Complexity

• Time complexity: O(m * n)
• Space complexity: O(m * n)

Where m is the number of rows and n is the number of columns in the given matrix.

Things to watch for

Using a Visited Array Instead of Value Comparison

Unlike typical graph traversal problems, this problem does not require a visited array. The strictly increasing constraint naturally prevents revisiting cells since you cannot go back to a smaller value. Using a visited array unnecessarily complicates the solution and can cause bugs when the same cell should be explored from different starting points.

Forgetting to Try All Starting Cells

The longest increasing path might not start from any corner or edge cell. You must try starting the DFS from every cell in the matrix and track the global maximum. A common mistake is assuming the path starts from the minimum or maximum value cell.

Incorrect Memoization Key

When memoizing results, the cache key should be just the cell coordinates (r, c), not including the previous value. The longest path starting from a cell is independent of how you reached that cell because you can only move to strictly larger values. Including prevVal in the cache key wastes memory and misses cache hits.

Using Non-Strict Inequality

The problem requires strictly increasing values. Using >= instead of > when comparing neighboring cells allows equal values to be included in the path, which violates the problem constraints and leads to incorrect answers or infinite loops.

Not Handling Edge Cases for Small Matrices

For a 1x1 matrix, the answer is always 1. Some solutions fail to handle this case properly, especially when the logic assumes there will always be valid neighbors to explore.

from typing import List
from collections import deque

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        indegree = [[0] * COLS for _ in range(ROWS)]

        for r in range(ROWS):
            for c in range(COLS):
                for d in directions:
                    nr, nc = d[0] + r, d[1] + c
                    if (0 <= nr < ROWS and 0 <= nc < COLS and
                        matrix[nr][nc] < matrix[r][c]
                    ):
                        indegree[r][c] += 1

        q = deque()
        for r in range(ROWS):
            for c in range(COLS):
                if indegree[r][c] == 0:
                    q.append([r, c])

        LIS = 0
        while q:
            for _ in range(len(q)):
                r, c = q.popleft()
                for d in directions:
                    nr, nc = r + d[0], c + d[1]
                    if (0 <= nr < ROWS and 0 <= nc < COLS and
                        matrix[nr][nc] > matrix[r][c]
                    ):
                        indegree[nr][nc] -= 1
                        if indegree[nr][nc] == 0:
                            q.append([nr, nc])
            LIS += 1
        return LIS

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int ROWS = matrix.size(), COLS = matrix[0].size();
        vector<vector<int>> indegree(ROWS, vector<int>(COLS, 0));
        vector<vector<int>> directions = {{-1, 0}, {1, 0},
                                          {0, -1}, {0, 1}};

        for (int r = 0; r < ROWS; ++r) {
            for (int c = 0; c < COLS; ++c) {
                for (auto& d : directions) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < ROWS && nc >= 0 &&
                        nc < COLS && matrix[nr][nc] < matrix[r][c]) {
                        indegree[r][c]++;
                    }
                }
            }
        }

        queue<pair<int, int>> q;
        for (int r = 0; r < ROWS; ++r) {
            for (int c = 0; c < COLS; ++c) {
                if (indegree[r][c] == 0) {
                    q.push({r, c});
                }
            }
        }

        int LIS = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                auto [r, c] = q.front();
                q.pop();
                for (auto& d : directions) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < ROWS && nc >= 0 &&
                        nc < COLS && matrix[nr][nc] > matrix[r][c]) {
                        if (--indegree[nr][nc] == 0) {
                            q.push({nr, nc});
                        }
                    }
                }
            }
            LIS++;
        }
        return LIS;
    }
};