What is the brute force approach and complexity for Longest Increasing Path in a Matrix?

From each cell, try every bigger neighbour again and again; nothing is saved between searches with time complexity O(4^(R · C)) and space complexity O(R · C).

What is the optimal approach and complexity for Longest Increasing Path in a Matrix?

Save each cell's longest path; any later search that reaches the cell reuses the saved value with optimal time complexity O(R · C) and space complexity O(R · C).

How do you identify the pattern for Longest Increasing Path in a Matrix?

Look for key signals in the prompt: "strictly increasing path" indicates Values only go up along a path, so the 'move to a bigger neighbour' graph has no cycles. It is a DAG.; "up, down, left, right" indicates Each cell has up to four edges to its neighbours. The grid is a graph.; "length of the longest path" indicates The longest path from each node, then the maximum over all nodes. That is DAG DP with a memo..

Longest Increasing Path in a Matrix

Hard·LeetCode #329 Pro OnlyMedium

LeetCode

Problem Statement

You are given an m × n grid of integers. From a cell you may step up, down, left or right to a neighbouring cell. Diagonal steps are not allowed, and you cannot leave the grid.

A path is increasing if every step goes to a cell with a strictly bigger value. Find the longest increasing path that starts from any cell, and return its length, counted in cells.

Input

matrix, an m × n grid of integers.

Output

The number of cells in the longest strictly increasing path.

Example 1

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]

Output: 4

The longest path is 1 → 2 → 6 → 9. Each step moves to a neighbouring cell with a bigger value.

Example 2

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

Output: 4

The path 3 → 4 → 5 → 6 runs along the top row and then down the right side. Diagonal steps are not allowed.

Example 3

Input: matrix = [[1]]

Output: 1

A single cell is a path of length 1.

Constraints

• m == matrix.length
• n == matrix[i].length
• 1 ≤ m, n ≤ 200
• 0 ≤ matrix[i][j] ≤ 2^31 − 1

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“strictly increasing path”

→ Values only go up along a path, so the 'move to a bigger neighbour' graph has no cycles. It is a DAG.

“up, down, left, right”

→ Each cell has up to four edges to its neighbours. The grid is a graph.

“length of the longest path”

→ The longest path from each node, then the maximum over all nodes. That is DAG DP with a memo.

Approach Complexity Ladder

Brute Force — DFS from every cell, no memoryO(4^(R · C))O(R · C)

From each cell, try every bigger neighbour again and again; nothing is saved between searches

Optimal — memoised DFS: each cell's answer is computed onceO(R · C)O(R · C)

Save each cell's longest path; any later search that reaches the cell reuses the saved value

Brute Force Intuition

Start a DFS at every cell. From the current cell, move to each neighbour with a bigger value and continue from there. Keep the longest path found. Nothing is remembered, so the same cells are explored again from every path that reaches them.

Recognition rule for this sub-pattern:

Post-order DFS gives reverse topological order; memoised DFS computes values along a DAG.

Remember this · Topological Sort

Trigger

Prerequisites, dependencies, build order, "can all courses be finished?", ordering letters from sorted words.

Think

Is this a directed graph where some things must happen before others?

Key question

Which nodes currently have in-degree 0?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Topological Sort translate into production architectures and low-level memory mechanics.

LLD Practice

Task Scheduler & Workflow Orchestrator

Resolving DAG build pipelines and asynchronous task dependency resolution.

Explore Track

C++ Internals

Static vs Global Linkage & Init Order Fiasco

Why compilers resolve static global variables as a DAG to prevent runtime crashes.

Explore Track

Loud and Rich