329. Longest Increasing Path In a Matrix - Explanation

Description

You are given a 2-D grid of integers matrix, where each integer is greater than or equal to 0.

Return the length of the longest strictly increasing path within matrix.

From each cell within the path, you can move either horizontally or vertically. You may not move diagonally.

Example 1:

Input: matrix = [[5,5,3],[2,3,6],[1,1,1]]

Output: 4

Explanation: The longest increasing path is [1, 2, 3, 6] or [1, 2, 3, 5].

Example 2:

Input: matrix = [[1,2,3],[2,1,4],[7,6,5]]

Output: 7

Explanation: The longest increasing path is [1, 2, 3, 4, 5, 6, 7].

Constraints:

1 <= matrix.length, matrix[i].length <= 100

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the given matrix.

Hint 1

If we move from one cell to an adjacent cell with a greater value, we won't revisit a cell, as the path is strictly increasing. A brute force approach would be to run a dfs from every cell and return the longest path found. This approach is exponential. Can you think of a way to optimize it to avoid redundant calculations?

Hint 2

We can use memoization to cache the results of recursive calls and avoid redundant computations. A hash map or a 2D array can be used to store these results.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Depth-First Search (DFS) - The solution explores paths in a grid using recursive DFS with 4-directional movement
Dynamic Programming with Memoization - Caching results for each cell to avoid redundant path computations
Topological Sort (Kahn's Algorithm) - An alternative BFS approach using indegrees to process cells in dependency order
Graph Concepts (DAG) - Understanding that strictly increasing values create a directed acyclic graph structure

1. Recursion

Intuition

We need the length of the longest path in the matrix where values strictly increase at every step. From any cell, we can move up, down, left, or right.

A natural way to solve this is to try starting from every cell and explore all increasing paths using DFS.
For a given cell, we keep walking to neighboring cells only if the next value is greater than the current one.

The recursive function represents:
"What is the longest increasing path starting from cell (r, c), given that the previous value was prevVal?"

If the move goes out of bounds or the next value is not strictly larger than prevVal, that path ends.

Algorithm

Store the 4 possible movement directions (up, down, left, right).
Define a recursive function dfs(r, c, prevVal):
- If (r, c) is outside the grid, or matrix[r][c] <= prevVal, return 0
- Otherwise, start with res = 1 (the current cell counts as length 1)
- Try all 4 directions and take the maximum:
  - 1 + dfs(next_r, next_c, matrix[r][c])
For every cell in the matrix:
- Call dfs(r, c, -infinity) so the first cell is always allowed
- Track the maximum result over all starting cells
Return that maximum length

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]]

        def dfs(r, c, prevVal):
            if (min(r, c) < 0 or r >= ROWS or
                c >= COLS or matrix[r][c] <= prevVal
            ):
                return 0

            res = 1
            for d in directions:
                res = max(res, 1 + dfs(r + d[0], c + d[1], matrix[r][c]))
            return res

        LIP = 0
        for r in range(ROWS):
            for c in range(COLS):
                LIP = max(LIP, dfs(r, c, float('-inf')))
        return LIP

class Solution {
public:
    vector<vector<int>> directions = {{-1, 0}, {1, 0},
                                      {0, -1}, {0, 1}};

    int dfs(vector<vector<int>>& matrix, int r, int c, int prevVal) {
        int ROWS = matrix.size(), COLS = matrix[0].size();
        if (r < 0 || r >= ROWS || c < 0 ||
            c >= COLS || matrix[r][c] <= prevVal)
            return 0;

        int res = 1;
        for (auto d : directions)
            res = max(res, 1 + dfs(matrix, r + d[0],
                                   c + d[1], matrix[r][c]));
        return res;
    }

    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int ROWS = matrix.size(), COLS = matrix[0].size(), LIP = 0;
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                LIP = max(LIP, dfs(matrix, r, c, INT_MIN));
            }
        }
        return LIP;
    }
};

class Solution {
    /**
     * @param {number[][]} matrix
     * @return {number}
     */
    longestIncreasingPath(matrix) {
        const directions = [
            [-1, 0],
            [1, 0],
            [0, -1],
            [0, 1],
        ];
        const ROWS = matrix.length,
            COLS = matrix[0].length;

        const dfs = (r, c, prevVal) => {
            if (
                r < 0 ||
                r >= ROWS ||
                c < 0 ||
                c >= COLS ||
                matrix[r][c] <= prevVal
            ) {
                return 0;
            }

            let res = 1;
            for (let d of directions) {
                res = Math.max(res, 1 + dfs(r + d[0], c + d[1], matrix[r][c]));
            }
            return res;
        };

        let LIP = 0;
        for (let r = 0; r < ROWS; r++) {
            for (let c = 0; c < COLS; c++) {
                LIP = Math.max(LIP, dfs(r, c, -Infinity));
            }
        }
        return LIP;
    }
}

class Solution {
    private val directions = arrayOf(
        intArrayOf(-1, 0), intArrayOf(1, 0),
        intArrayOf(0, -1), intArrayOf(0, 1)
    )

    fun longestIncreasingPath(matrix: Array<IntArray>): Int {
        val rows = matrix.size
        val cols = matrix[0].size

        fun dfs(r: Int, c: Int, prevVal: Int): Int {
            if (r < 0 || r >= rows || c < 0 || c >= cols ||
                matrix[r][c] <= prevVal) {
                return 0
            }

            var res = 1
            for (d in directions) {
                res = maxOf(res, 1 + dfs(r + d[0], c + d[1], matrix[r][c]))
            }
            return res
        }

        var LIP = 0
        for (r in 0 until rows) {
            for (c in 0 until cols) {
                LIP = maxOf(LIP, dfs(r, c, Int.MIN_VALUE))
            }
        }
        return LIP
    }
}

Time & Space Complexity

Time complexity: $O(m * n * 4 ^ {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$ .

2. Dynamic Programming (Top-Down)

Intuition

We want the length of the longest path in a grid where every move goes to a strictly larger value, and we can move in 4 directions (up, down, left, right).

A plain dfs tries many paths repeatedly. The key improvement is to notice this:

If we start from the same cell (r, c), the best (longest) increasing path from that cell is always the same.

So instead of recomputing it again and again, we store it in a cache (dp).

The recursive function is still dfs, but now it represents:
"What is the longest increasing path starting from cell (r, c)?"

We only move to neighbors that have a larger value than the current cell, and we memoize the result for each cell.

Algorithm

Create a map dp to cache results:
- dp[(r, c)] = length of the longest increasing path starting from (r, c)
Define a DFS function dfs(r, c, prevVal):
- If (r, c) is out of bounds, or matrix[r][c] <= prevVal, return 0
- If (r, c) is already in dp, return dp[(r, c)] (reuse the cached answer)
Otherwise, compute the answer for (r, c):
- Start with res = 1 (path length including the current cell)
- Try moving in all 4 directions and take the best valid extension:
  - res = max(res, 1 + dfs(nr, nc, matrix[r][c]))
Store the computed value in dp[(r, c)] and return it
Call dfs from every cell to ensure all dp values are filled
The final answer is the maximum value stored in dp

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        dp = {}  # (r, c) -> LIP

        def dfs(r, c, prevVal):
            if (r < 0 or r == ROWS or c < 0 or
                c == COLS or matrix[r][c] <= prevVal
            ):
                return 0
            if (r, c) in dp:
                return dp[(r, c)]

            res = 1
            res = max(res, 1 + dfs(r + 1, c, matrix[r][c]))
            res = max(res, 1 + dfs(r - 1, c, matrix[r][c]))
            res = max(res, 1 + dfs(r, c + 1, matrix[r][c]))
            res = max(res, 1 + dfs(r, c - 1, matrix[r][c]))
            dp[(r, c)] = res
            return res

        for r in range(ROWS):
            for c in range(COLS):
                dfs(r, c, -1)
        return max(dp.values())

class Solution {
public:
    vector<vector<int>> directions = {{-1, 0}, {1, 0},
                                      {0, -1}, {0, 1}};
    vector<vector<int>> dp;

    int dfs(vector<vector<int>>& matrix, int r, int c, int prevVal) {
        int ROWS = matrix.size(), COLS = matrix[0].size();
        if (r < 0 || r >= ROWS || c < 0 ||
            c >= COLS || matrix[r][c] <= prevVal) {
            return 0;
        }
        if (dp[r][c] != -1) return dp[r][c];

        int res = 1;
        for (vector<int> d : directions) {
            res = max(res, 1 + dfs(matrix, r + d[0],
                               c + d[1], matrix[r][c]));
        }
        dp[r][c] = res;
        return res;
    }

    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int ROWS = matrix.size(), COLS = matrix[0].size();
        dp = vector<vector<int>>(ROWS, vector<int>(COLS, -1));
        int LIP = 0;

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                LIP = max(LIP, dfs(matrix, r, c, INT_MIN));
            }
        }
        return LIP;
    }
};

class Solution {
    /**
     * @param {number[][]} matrix
     * @return {number}
     */
    longestIncreasingPath(matrix) {
        const directions = [
            [-1, 0],
            [1, 0],
            [0, -1],
            [0, 1],
        ];
        const ROWS = matrix.length,
            COLS = matrix[0].length;
        let dp = Array.from({ length: ROWS }, () => Array(COLS).fill(-1));

        const dfs = (r, c, prevVal) => {
            if (
                r < 0 ||
                r >= ROWS ||
                c < 0 ||
                c >= COLS ||
                matrix[r][c] <= prevVal
            ) {
                return 0;
            }
            if (dp[r][c] !== -1) return dp[r][c];

            let res = 1;
            for (let d of directions) {
                res = Math.max(res, 1 + dfs(r + d[0], c + d[1], matrix[r][c]));
            }
            dp[r][c] = res;
            return res;
        };

        let LIP = 0;
        for (let r = 0; r < ROWS; r++) {
            for (let c = 0; c < COLS; c++) {
                LIP = Math.max(LIP, dfs(r, c, -Infinity));
            }
        }
        return LIP;
    }
}

func longestIncreasingPath(matrix [][]int) int {
    rows, cols := len(matrix), len(matrix[0])
    dp := make([][]int, rows)
    for i := range dp {
        dp[i] = make([]int, cols)
    }

    var dfs func(r, c, prevVal int) int
    dfs = func(r, c, prevVal int) int {
        if r < 0 || r >= rows || c < 0 || c >= cols ||
           matrix[r][c] <= prevVal {
            return 0
        }
        if dp[r][c] != 0 {
            return dp[r][c]
        }

        res := 1
        res = max(res, 1 + dfs(r+1, c, matrix[r][c]))
        res = max(res, 1 + dfs(r-1, c, matrix[r][c]))
        res = max(res, 1 + dfs(r, c+1, matrix[r][c]))
        res = max(res, 1 + dfs(r, c-1, matrix[r][c]))
        dp[r][c] = res
        return res
    }

    maxPath := 0
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            maxPath = max(maxPath, dfs(r, c, -1))
        }
    }
    return maxPath
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
    fun longestIncreasingPath(matrix: Array<IntArray>): Int {
        val rows = matrix.size
        val cols = matrix[0].size
        val dp = Array(rows) { IntArray(cols) }

        fun dfs(r: Int, c: Int, prevVal: Int): Int {
            if (r < 0 || r >= rows || c < 0 || c >= cols ||
                matrix[r][c] <= prevVal) {
                return 0
            }
            if (dp[r][c] != 0) {
                return dp[r][c]
            }

            var res = 1
            res = maxOf(res, 1 + dfs(r + 1, c, matrix[r][c]))
            res = maxOf(res, 1 + dfs(r - 1, c, matrix[r][c]))
            res = maxOf(res, 1 + dfs(r, c + 1, matrix[r][c]))
            res = maxOf(res, 1 + dfs(r, c - 1, matrix[r][c]))
            dp[r][c] = res
            return res
        }

        var maxPath = 0
        for (r in 0 until rows) {
            for (c in 0 until cols) {
                maxPath = maxOf(maxPath, dfs(r, c, -1))
            }
        }
        return maxPath
    }
}

class Solution {
    func longestIncreasingPath(_ matrix: [[Int]]) -> Int {
        let rows = matrix.count, cols = matrix[0].count
        var dp = Array(repeating: Array(repeating: -1, count: cols), count: rows)

        func dfs(_ r: Int, _ c: Int, _ prevVal: Int) -> Int {
            if r < 0 || r >= rows || c < 0 || c >= cols || matrix[r][c] <= prevVal {
                return 0
            }
            if dp[r][c] != -1 {
                return dp[r][c]
            }

            var res = 1
            res = max(res, 1 + dfs(r + 1, c, matrix[r][c]))
            res = max(res, 1 + dfs(r - 1, c, matrix[r][c]))
            res = max(res, 1 + dfs(r, c + 1, matrix[r][c]))
            res = max(res, 1 + dfs(r, c - 1, matrix[r][c]))

            dp[r][c] = res
            return res
        }

        var maxPath = 0
        for r in 0..<rows {
            for c in 0..<cols {
                maxPath = max(maxPath, dfs(r, c, -1))
            }
        }
        return maxPath
    }
}

Time & Space 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$ .

3. Topological Sort (Kahn's Algorithm)

Intuition

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.

Algorithm

Treat each cell (r, c) as a node.
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
Initialize a queue with all cells that have indegree 0:
- these are local minima and can start an increasing path
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)
When the queue becomes empty, all nodes have been processed.
Return the number of layers processed (LIS), which equals the longest increasing path length.

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

public class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        int ROWS = matrix.length, COLS = matrix[0].length;
        int[][] indegree = new int[ROWS][COLS];
        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 (int[] 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<int[]> q = new LinkedList<>();
        for (int r = 0; r < ROWS; ++r) {
            for (int c = 0; c < COLS; ++c) {
                if (indegree[r][c] == 0) {
                    q.offer(new int[]{r, c});
                }
            }
        }

        int LIS = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                int[] node = q.poll();
                int r = node[0], c = node[1];
                for (int[] 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.offer(new int[]{nr, nc});
                        }
                    }
                }
            }
            LIS++;
        }
        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;
    }
};

class Solution {
    /**
     * @param {number[][]} matrix
     * @return {number}
     */
    longestIncreasingPath(matrix) {
        const ROWS = matrix.length,
            COLS = matrix[0].length;
        const directions = [
            [-1, 0],
            [1, 0],
            [0, -1],
            [0, 1],
        ];
        let indegree = Array.from({ length: ROWS }, () => Array(COLS).fill(0));

        for (let r = 0; r < ROWS; r++) {
            for (let c = 0; c < COLS; c++) {
                for (const [dr, dc] of directions) {
                    const nr = r + dr,
                        nc = c + dc;
                    if (
                        nr >= 0 &&
                        nr < ROWS &&
                        nc >= 0 &&
                        nc < COLS &&
                        matrix[nr][nc] < matrix[r][c]
                    ) {
                        indegree[r][c]++;
                    }
                }
            }
        }

        let q = new Queue();
        for (let r = 0; r < ROWS; r++) {
            for (let c = 0; c < COLS; c++) {
                if (indegree[r][c] === 0) {
                    q.push([r, c]);
                }
            }
        }

        let LIS = 0;
        while (!q.isEmpty()) {
            const size = q.size();
            for (let i = 0; i < size; i++) {
                const [r, c] = q.pop();
                for (const [dr, dc] of directions) {
                    const nr = r + dr,
                        nc = c + dc;
                    if (
                        nr >= 0 &&
                        nr < ROWS &&
                        nc >= 0 &&
                        nc < COLS &&
                        matrix[nr][nc] > matrix[r][c]
                    ) {
                        indegree[nr][nc]--;
                        if (indegree[nr][nc] === 0) {
                            q.push([nr, nc]);
                        }
                    }
                }
            }
            LIS++;
        }
        return LIS;
    }
}

public class Solution {
    public int LongestIncreasingPath(int[][] matrix) {
        int ROWS = matrix.Length, COLS = matrix[0].Length;
        int[][] indegree = new int[ROWS][];
        for (int i = 0; i < ROWS; i++) {
            indegree[i] = new int[COLS];
        }
        int[][] directions = new int[][] {
            new int[] { -1, 0 }, new int[] { 1, 0 },
            new int[] { 0, -1 }, new int[] { 0, 1 }
        };

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                foreach (var d in 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<int[]> q = new Queue<int[]>();
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (indegree[r][c] == 0) {
                    q.Enqueue(new int[] { r, c });
                }
            }
        }

        int LIS = 0;
        while (q.Count > 0) {
            int size = q.Count;
            for (int i = 0; i < size; i++) {
                int[] node = q.Dequeue();
                int r = node[0], c = node[1];
                foreach (var d in 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.Enqueue(new int[] { nr, nc });
                        }
                    }
                }
            }
            LIS++;
        }
        return LIS;
    }
}

func longestIncreasingPath(matrix [][]int) int {
    rows, cols := len(matrix), len(matrix[0])
    indegree := make([][]int, rows)
    for i := range indegree {
        indegree[i] = make([]int, cols)
    }

    directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            for _, d := range directions {
                nr, nc := r + d[0], c + d[1]
                if nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
                   matrix[nr][nc] < matrix[r][c] {
                    indegree[r][c]++
                }
            }
        }
    }

    queue := [][]int{}
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if indegree[r][c] == 0 {
                queue = append(queue, []int{r, c})
            }
        }
    }

    lis := 0
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            r, c := node[0], node[1]
            for _, d := range directions {
                nr, nc := r + d[0], c + d[1]
                if nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
                   matrix[nr][nc] > matrix[r][c] {
                    indegree[nr][nc]--
                    if indegree[nr][nc] == 0 {
                        queue = append(queue, []int{nr, nc})
                    }
                }
            }
        }
        lis++
    }

    return lis
}

class Solution {
    fun longestIncreasingPath(matrix: Array<IntArray>): Int {
        val rows = matrix.size
        val cols = matrix[0].size
        val indegree = Array(rows) { IntArray(cols) }
        val directions = arrayOf(intArrayOf(-1, 0), intArrayOf(1, 0),
                                 intArrayOf(0, -1), intArrayOf(0, 1))

        for (r in 0 until rows) {
            for (c in 0 until cols) {
                for (d in directions) {
                    val nr = r + d[0]
                    val nc = c + d[1]
                    if (nr in 0 until rows && nc in 0 until cols &&
                        matrix[nr][nc] < matrix[r][c]) {
                        indegree[r][c]++
                    }
                }
            }
        }

        val queue: Queue<IntArray> = LinkedList()
        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (indegree[r][c] == 0) {
                    queue.offer(intArrayOf(r, c))
                }
            }
        }

        var lis = 0
        while (queue.isNotEmpty()) {
            repeat(queue.size) {
                val (r, c) = queue.poll()
                for (d in directions) {
                    val nr = r + d[0]
                    val nc = c + d[1]
                    if (nr in 0 until rows && nc in 0 until cols &&
                        matrix[nr][nc] > matrix[r][c]) {
                        if (--indegree[nr][nc] == 0) {
                            queue.offer(intArrayOf(nr, nc))
                        }
                    }
                }
            }
            lis++
        }

        return lis
    }
}

Time & Space 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$ .

Common Pitfalls

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.