Skip to content

Volume ITechnology

4.24.7 — Longest Increasing Path in a Matrix ​

LeetCode 329 · Hard

The problem ​

Find the length of the longest path in a matrix where every step moves to an adjacent cell with a strictly larger value. You may move up, down, left or right, and you may not move diagonally or wrap around.

[[9,9,4],
 [6,6,8],
 [2,1,1]]      →  4     (1 → 2 → 6 → 9)

Constraints:

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

Plain-English Restatement: You're dropped onto a grid of mountains of varying heights. You want to take the longest possible hike. The catch is you can only step up to a higher elevation, never down or flat, and you can only move North, South, East, or West. What is the maximum number of steps you can take?

Brute Force Approach: You could write a recursive DFS that starts at every single cell and explores all valid increasing paths, returning the max length found.

  • Time Complexity: O(V \cdot 4^V) where V = m \times n. In the worst case, the matrix could be heavily branched. Without caching, you'd trace every overlapping path from scratch.
  • Why it's wasteful: If you start at cell A and hike to cell B, and you eventually find the longest path from B is 10 steps, you should remember that. Later, if you start at cell C and hike to cell B, you shouldn't re-calculate the path from B.

The pattern ​

This is DP, but the fill order is not obvious. In a normal grid DP you fill top to bottom; here a path can go in any direction, so there is no row or column ordering that guarantees the cells you need are ready.

That is exactly when memoised recursion wins. Write the recursion and let it discover the order:

\text{longest}(r, c) = 1 + \max\big(\text{longest}(nr, nc)\ :\ \text{neighbour is strictly larger}\big)

and 1 if no neighbour is larger.

No visited set is needed, and no undo. Because every step must strictly increase, a path can never return to a cell it has already used — the values would have to decrease. The strict increase makes the graph acyclic, and that is what makes memoisation valid at all.

Say that out loud: the "strictly increasing" condition means this is a DAG, so each cell's answer is a fixed number and can be cached. Without it, the answer would depend on the path taken to get there and no cache would be sound.

The solution ​

python
class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:  # (1)
            return 0
        rows, cols = len(matrix), len(matrix[0])
        memo = {}  # (2)

        def longest(r: int, c: int) -> int:  # (3)
            if (r, c) in memo:  # (4)
                return memo[(r, c)]

            best = 1                                   # (5) the cell alone
            for nr, nc in ((r+1,c), (r-1,c), (r,c+1), (r,c-1)):  # (6)
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:  # (7)
                    best = max(best, 1 + longest(nr, nc))  # (8)

            memo[(r, c)] = best  # (9)
            return best

        return max(longest(r, c) for r in range(rows) for c in range(cols))  # (10)
ts
function longestIncreasingPath(matrix: number[][]): number {
  if (!matrix.length) return 0;  // (1)
  const rows = matrix.length, cols = matrix[0].length;
  const memo = Array.from({ length: rows }, () => new Array(cols).fill(0));  // (2)

  function longest(r: number, c: number): number {  // (3)
    if (memo[r][c]) return memo[r][c];  // (4)

    let best = 1;  // (5)
    for (const [nr, nc] of [[r+1,c],[r-1,c],[r,c+1],[r,c-1]] as [number,number][]) {  // (6)
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] > matrix[r][c]) {  // (7)
        best = Math.max(best, 1 + longest(nr, nc));  // (8)
      }
    }

    memo[r][c] = best;  // (9)
    return best;
  }

  let answer = 0;  // (10)
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      answer = Math.max(answer, longest(r, c));

  return answer;
}

Line by line ​

(1) An empty grid has no path.

(2) The memory. memo[(r, c)] will hold the length of the longest increasing path that starts at cell (r, c). Each cell's answer is worked out once and then reused.

(3) longest(r, c) returns the longest increasing path starting at (r, c).

(4) Already worked out? Return the stored answer. This is what turns an exponential search into a linear one.

(5) The cell on its own is a path of length 1.

(6) Look at the four neighbours.

(7) Only step to a neighbour that is on the grid and strictly bigger.

(8) A path starting here can step to that neighbour and continue with the neighbour's best path. That gives 1 + longest(neighbour). Keep the longest option.

(9) Store the answer before returning it.

(10) The longest path can start anywhere, so try every cell. Thanks to the memory, most of these calls just read a stored answer.

Why is there no "visited" marking, as in Word Search? Because each step goes to a strictly bigger number. A path can never come back to a cell it has already used, because that would need a number to be bigger than itself. So loops are impossible, and the answer for a cell never depends on itself.

memo[r][c] starting at 0 doubles as "not computed", because every real answer is at least 1. That is a neat use of a value that cannot occur.

best starts at 1, since the cell itself is a path of length one.

Try every starting cell, because the longest path can begin anywhere — and thanks to the cache, later starts mostly hit precomputed answers.

No visited marking anywhere, and no restore. Compare 4.18.6 Word Search, which needs both because its paths can revisit cells in principle. Here the strict increase does the job for free, and knowing why is the difference between copying this solution and understanding it.

Edge cases ​

  • One cell. The answer is 1.
  • All cells equal. No step is strictly bigger, so every path has length 1.
  • A grid that increases in a snake, visiting every cell. The answer is rows × cols, and the recursion can be that many calls deep.

Complexity ​

O(rows \times cols) time. Each cell is computed once, and each computation looks at four neighbours — a constant.

O(rows \times cols) space for the cache and the recursion depth.

Without memoisation it is exponential, because the same cell is recomputed once per path reaching it.

The topological-sort alternative ​

There is also a bottom-up version, and it makes the DAG explicit.

Treat each cell as a node with an edge to every strictly larger neighbour. Compute each cell's outdegree — how many larger neighbours it has — and start from the cells with outdegree 0, which are the local maxima and can only end a path.

Then peel layer by layer, exactly like Kahn's algorithm in 4.20.9. The number of layers is the answer.

O(rows \times cols), iterative, no recursion depth risk. On a 200×200 grid the memoised version can be 40,000 frames deep, which is a genuine reason to prefer this one.

Mention it; write the memoised version. It is shorter and easier to explain.

Where this goes next ​

  • Word Search — grid DFS that does need backtracking, because its paths have no monotonic constraint. The contrast is the lesson. 4.18.6.
  • Longest Increasing Subsequence — the 1-D version, and it has an O(n \log n) trick that has no grid equivalent. 4.23.11.
  • Course Schedule II — the topological peeling above. 4.20.9.
  • Cherry Pickup, Minimum Falling Path Sum — grid DPs where the fill order is obvious, for contrast.

The rule: memoised recursion is the right form when the dependency order is hard to see. Bottom-up tabulation requires you to work the order out yourself; top-down discovers it. That is the point of having both forms in 4.22.

What the interviewer will push on ​

"Why is no visited set needed?" Strictly increasing values make cycles impossible.

"Why is memoisation valid?" The answer for a cell does not depend on how you arrived, because the graph is a DAG.

"Why top-down rather than bottom-up?" There is no obvious order to fill a table in; the recursion finds one.

"What is the complexity, and why is it not exponential?" Each cell is computed once. Without the cache it would be.

"What about stack depth?" Up to rows × cols frames. The topological version avoids it.

"Why start from every cell?" The longest path can begin anywhere, and the cache makes the repeated starts cheap.

One thing to volunteer: name the DAG. "Strictly increasing means the graph is acyclic, which is what makes the cache sound and the visited set unnecessary." That single sentence explains three of the design decisions at once.

Next: 4.24.8 Distinct Subsequences — back to the two-string grid, counting instead of measuring.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet