Longest Increasing Path in a Matrix

Given an m × n grid of integers, find the length of the longest strictly increasing path. At each step you can move up, down, left, or right — no diagonals, no wrapping around the edges.

• 1 ≤ m, n ≤ 100 — up to 10,000 cells
• Values are non-negative integers (no negatives to trip you up)
• Each step must go to a strictly larger value — equal neighbors don't count

Examples

How to think about it

Forget that it's a grid for a moment. What you actually have is a directed graph: every cell is a node, and there's a directed edge from cell A to cell B if B is an adjacent neighbor with a strictly larger value. Because values must strictly increase, you can never go in a circle — it's a DAG.

Finding the longest path in a DAG is a classic problem. The catch is that you have up to 10,000 nodes and you can start anywhere. If you naively run DFS from every cell, you'll recompute the same sub-paths over and over. The fix is simple: remember the answer for each cell the first time you compute it.

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.

Decision Tree

Algorithm

1. Store the 4 possible movement directions (up, down, left, right).
2. 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])
3. 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.
4. Return that maximum length.

def longestIncreasingPath(matrix):
    ROWS, COLS = len(matrix), len(matrix[0])
    dirs = [[-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 dirs:
            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

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:

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

1. Create a map dp to cache results: dp[(r, c)] = length of the longest increasing path starting from (r, c)
2. 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).
3. 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.
4. Call dfs from every cell to ensure all dp values are filled.
5. The final answer is the maximum value stored in dp.

def longestIncreasingPath(matrix):
    ROWS, COLS = len(matrix), len(matrix[0])
    dp = {}  # (r, c) → longest path from here

    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:          # already solved — reuse
            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())

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

1. Treat each cell (r, c) as a node.
2. Compute 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. Return the number of layers processed (LIS), which equals the longest increasing path length.

from collections import deque

def longestIncreasingPath(matrix):
    ROWS, COLS = len(matrix), len(matrix[0])
    dirs = [[-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 dirs:
                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(
        [r, c] for r in range(ROWS)
               for c in range(COLS)
               if indegree[r][c] == 0
    )

    LIP = 0
    while q:
        for _ in range(len(q)):
            r, c = q.popleft()
            for d in dirs:
                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])
        LIP += 1
    return LIP

Complexity Comparison

Both O(m·n) solutions are equally fast in practice. The memoization approach is cleaner to explain in an interview. The topo sort approach is useful if you're uncomfortable with recursion depth on large grids (Python's default recursion limit is 1,000 — a 100×100 grid can exceed it in the brute force version).

When does this pattern show up?

Any time a problem asks for the longest or shortest path in a grid or graph where the direction of travel is determined by the values themselves, you're likely looking at DFS + memoization on a DAG.

Signs you're looking at this pattern

• Grid problem asking for a "longest path" or "maximum chain" — not shortest path (that's BFS).
• Movement is restricted by value: you can only go somewhere strictly greater (or smaller, or within some delta).
• No "visited" array needed — value constraints naturally prevent cycles.
• You're calling the same DFS from many starting points and noticing you're re-solving the same cells.

Reading the constraints

• m, n ≤ 100 — 10,000 cells. O(m·n) is obviously fine. O(m²·n²) might just barely squeeze through. O(m·n·4^(m·n)) is instant death.
• "Strictly increasing" — equal values don't extend the path. This is what makes the graph a DAG and lets memoization work cleanly.
• Values are non-negative — you don't have to worry about negatives tricking you, but the path can start or end anywhere.

A real-world parallel

Routing water flow through terrain: a water molecule follows the path of steepest descent, moving from each cell to the lowest adjacent neighbor. The question "how far will water travel before it can't move?" is structurally identical to this problem — just reverse the inequality. Watershed modeling software solves exactly this problem on grids with millions of cells.

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.

What to do next

These problems share the same underlying structure — DFS/BFS on grids or DAGs with memoization or topological ordering.

• Word SearchMediumDFS on a grid — but with backtracking and a visited set (values don't prevent revisiting here).›
• Number of IslandsMediumGrid DFS fundamentals. Warm-up for any matrix traversal problem.›
• Longest Increasing SubsequenceMediumSame "strictly increasing" constraint in 1D instead of 2D. Classic DP.›
• Course ScheduleMediumCycle detection in a DAG. Core skill for topological sort approach.›
• Coin ChangeMediumMemoized recursion on a different kind of DAG. Builds the same muscle.›
• Pacific Atlantic Water FlowMediumMulti-source DFS on a matrix. Uses the same "increasing path" idea in reverse.›