329. Longest Increasing Path in a Matrix

At a Glance

Topic: dp-2d
Pattern: DFS + memoization on DAG (implicit graph from strict increase) + Dynamic Programming
Difficulty: Hard
Companies: Google, Amazon, Meta, Microsoft, Bloomberg
Frequency: High
LeetCode: 329

Problem (one-liner)

Given an m x n matrix of distinct integers, return the length of the longest strictly increasing path moving up, down, left, or right (no diagonal). You may start anywhere.

Recognition Cues

Longest path in a grid with a monotone rule (only move to larger values)
No cycles possible if moves are strict — state graph is a DAG → longest path = DP on DAG
“Start anywhere” = take max over all cells as path roots

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute DFS without memo — revisits explode — exponential.
Topo sort by value — process cells smallest-first, relax neighbors — O(mn) time and space.
DFS + memo — longestFrom[row][col] = 1 + max(neighbors that are larger) — O(mn) time, O(mn) space — optimal (each edge examined once per direction in aggregate).

Optimal Solution

Go

func longestIncreasingPath(matrix [][]int) int {
	rowCount := len(matrix)
	if rowCount == 0 {
		return 0
	}
	colCount := len(matrix[0])
	memo := make([][]int, rowCount)
	for row := range memo {
		memo[row] = make([]int, colCount)
		for col := range memo[row] {
			memo[row][col] = -1
		}
	}
	directions := [][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
	var dfs func(row, col int) int
	dfs = func(row, col int) int {
		if memo[row][col] != -1 {
			return memo[row][col]
		}
		best := 1
		current := matrix[row][col]
		for _, delta := range directions {
			nextRow, nextCol := row+delta[0], col+delta[1]
			if nextRow < 0 || nextRow >= rowCount || nextCol < 0 || nextCol >= colCount {
				continue
			}
			if matrix[nextRow][nextCol] <= current {
				continue
			}
			// Edge to strictly larger neighbor — DAG along decreasing-value reverse edges
			candidate := 1 + dfs(nextRow, nextCol)
			if candidate > best {
				best = candidate
			}
		}
		memo[row][col] = best
		return best
	}
	answer := 0
	for row := 0; row < rowCount; row++ {
		for col := 0; col < colCount; col++ {
			pathLen := dfs(row, col)
			if pathLen > answer {
				answer = pathLen
			}
		}
	}
	return answer
}

JavaScript

function longestIncreasingPath(matrix) {
  const rowCount = matrix.length;
  if (rowCount === 0) {
    return 0;
  }
  const colCount = matrix[0].length;
  const memo = Array.from({ length: rowCount }, () =>
    Array(colCount).fill(-1)
  );
  const directions = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ];
  function dfs(row, col) {
    if (memo[row][col] !== -1) {
      return memo[row][col];
    }
    let best = 1;
    const current = matrix[row][col];
    for (const [deltaRow, deltaCol] of directions) {
      const nextRow = row + deltaRow;
      const nextCol = col + deltaCol;
      if (
        nextRow < 0 ||
        nextRow >= rowCount ||
        nextCol < 0 ||
        nextCol >= colCount
      ) {
        continue;
      }
      if (matrix[nextRow][nextCol] <= current) {
        continue;
      }
      const candidate = 1 + dfs(nextRow, nextCol);
      if (candidate > best) {
        best = candidate;
      }
    }
    memo[row][col] = best;
    return best;
  }
  let answer = 0;
  for (let row = 0; row < rowCount; row += 1) {
    for (let col = 0; col < colCount; col += 1) {
      const pathLen = dfs(row, col);
      if (pathLen > answer) {
        answer = pathLen;
      }
    }
  }
  return answer;
}

Walkthrough

Matrix [[9,9,4],[6,6,8],[2,1,1]]. From bottom 1, move to 6 or 8 along increasing steps; longest chain length 4 (e.g. 1→2→6→9).

Invariant: memo[row][col] equals longest strictly increasing path starting at (row,col) following positive gradients only.

cell	value	neighbors larger	longestFrom
(2,2)	1	(1,2)=8, (2,1)=2	1+max(dfs)=…

Edge Cases

Single cell matrix — answer 1
Sorted row / column — path can span full snake depending on shape
Plateaus — problem states strictly increasing; equal neighbors are not edges (if duplicates allowed in variant, break ties carefully)

Pitfalls

Using plain visited bit without memo — need length per cell, not just seen
Allowing non-increasing moves — breaks DAG assumption
Stack overflow on huge grids in languages with low recursion limit — iterative topo order if needed

Variants

Non-strict increasing (allow equals) — edges multiply; may need cycle handling
Weighted longest path on DAG — replace 1+ with edge weights + topo order
3D grid / k directions — same memo pattern, more neighbors

Mind-Map Tags

#grid-dp #dag-longest-path #dfs-memo #strictly-increasing #implicit-graph