Skip to main content
Talentd

Longest Increasing Path in a Matrix - Solution & Explanation

HardArrayDynamic ProgrammingDepth-First SearchBreadth-First Search14 min readAsked at: Amazon, Microsoft, Apple +13
Practice this problem

Problem Statement

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

 

Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3:

Input: matrix = [[1]]
Output: 1

 

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • 0 <= matrix[i][j] <= 231 - 1

Approach Overview

Problem Overview: Given an m x n matrix, return the length of the longest strictly increasing path. From any cell you can move up, down, left, or right, but only to a cell with a larger value. The goal is to explore the grid efficiently without recomputing paths starting from the same cell.

Approach 1: Depth‑First Search (DFS) with Memoization (O(m*n) time, O(m*n) space)

Treat each cell as the start of a path and run DFS to explore neighbors with strictly larger values. The key insight: many paths overlap. If you already computed the longest path starting from a cell, reuse that result instead of recomputing it. Store results in a memo matrix where memo[r][c] represents the longest path beginning at that cell. Each cell is processed once, and every DFS only explores four directions. This converts an exponential search into linear work over all cells. This approach combines Depth‑First Search with Dynamic Programming via caching.

Approach 2: Topological Sort / BFS on Directed Graph (O(m*n) time, O(m*n) space)

Interpret the matrix as a directed graph. Create edges from smaller values to larger neighbors. Because values must increase, the graph is a DAG. Compute the outdegree for each cell (how many neighbors are larger). Cells with outdegree 0 represent path endpoints. Push them into a queue and perform level‑order processing similar to Kahn's algorithm. Each BFS layer represents one step backward in increasing paths. Reduce neighbor outdegrees as nodes are removed. The number of BFS layers processed equals the longest increasing path length. This reframes the grid as a graph problem with matrix traversal.

Recommended for interviews: DFS with memoization is the most commonly expected solution. It demonstrates understanding of DFS, caching overlapping subproblems, and converting exponential recursion into O(m*n) dynamic programming. Mentioning the topological sort interpretation shows deeper graph insight and can impress interviewers when discussing alternative formulations.

Approach 1: Depth First Search (DFS) with Memoization

This approach uses a combination of Depth First Search (DFS) and memoization to solve the problem efficiently. We explore each cell, attempting to find the longest increasing path starting from that cell. To avoid recalculating the path length for each call from the same cell, we use memoization to store already computed results.

In this Python solution, we define a helper function dfs that performs DFS on the matrix starting from a given cell. We utilize a memo table to store the longest path from each cell to avoid redundant calculations, improving performance significantly. The main function starts by iterating over each cell to compute the maximum length path by considering each cell as a starting point.

Code

PythonC++Java

Python

C++

Java

Complexity

The time complexity is O(m * n) because each cell is computed once and cached. The space complexity is also O(m * n) due to the memoization table.

Try this approach in the editor →

Approach 2: Dynamic Programming

This approach systematically calculates the longest increasing path dynamically by first iterating over the matrix and then updating results based on previously computed values. By using a dynamic programming table, we determine, for each cell, the longest chain it can contribute to incrementally.

The JavaScript solution uses dynamic programming. For each cell, the function dfs recursively explores valid neighbors, resulting in the longest increasing path starting from that cell. The result for each cell is stored in a DP table before being returned, which ensures efficiency by preventing the recalculation of already known results.

Code

JavaScriptC#

JavaScript

C#

Complexity

The time complexity is O(m * n) due to the fact that each matrix cell can be a starting point and is only calculated once with memoization guidance. The space complexity is O(m * n) because a result is stored for each cell in the DP table.

Try this approach in the editor →

Approach 3: Memoization Search

We design a function dfs(i, j), which represents the length of the longest increasing path that can be obtained starting from the coordinate (i, j) in the matrix. The answer is max_{i, j} dfs(i, j).

The execution logic of the function dfs(i, j) is as follows:

  • If (i, j) has been visited, directly return f(i, j);
  • Otherwise, search (i, j), search the coordinates (x, y) in four directions. If 0 \le x < m, 0 \le y < n and matrix[x][y] > matrix[i][j], then search (x, y). After the search is over, update f(i, j) to f(i, j) = max(f(i, j), f(x, y) + 1). Finally, return f(i, j).

The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the number of rows and columns of the matrix, respectively.

Similar problems:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Depth First Search (DFS) with Memoization

The time complexity is O(m * n) because each cell is computed once and cached. The space complexity is also O(m * n) due to the memoization table.

Dynamic Programming

The time complexity is O(m * n) due to the fact that each matrix cell can be a starting point and is only calculated once with memoization guidance. The space complexity is O(m * n) because a result is stored for each cell in the DP table.

Memoization Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS with MemoizationO(m*n)O(m*n)Best general solution. Clean recursion with caching avoids recomputation.
Topological Sort (BFS / Kahn's Algorithm)O(m*n)O(m*n)Useful when modeling the matrix as a DAG and processing nodes by levels.
Naive DFS without MemoizationO((m*n)*4^(m*n)) worst caseO(m*n)Conceptual baseline. Demonstrates the overlapping subproblem issue.

Video Solution

Longest Increasing Path in a Matrix - Leetcode 329 • NeetCode • 92,408 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Increasing Path in a Matrix easy or hard?
Longest Increasing Path in a Matrix is classified as a Hard problem on LeetCode. The difficulty comes from recognizing overlapping subproblems and transforming naive DFS into an efficient O(m*n) dynamic programming solution using memoization or graph topological ordering.
Longest Increasing Path in a Matrix Python/Java solution
Python and Java implementations typically use DFS with a memo table. A recursive function explores four directions and stores the computed longest path for each cell. This reduces the complexity to O(m*n) while keeping the implementation concise.
How to solve Longest Increasing Path in a Matrix in O(n)?
Treat the grid as m*n nodes and compute the longest path in O(m*n) time using DFS with memoization. Store the best path length starting from each cell in a cache so overlapping searches are avoided. Another O(m*n) method uses topological sorting by treating the matrix as a DAG and processing nodes by levels.
What is the best approach for Longest Increasing Path in a Matrix?
DFS with memoization is the most widely used approach. Start a DFS from every cell and cache the longest path length for that cell so repeated subproblems are not recomputed. Each cell is evaluated once, giving O(m*n) time and O(m*n) space complexity.
Is Longest Increasing Path in a Matrix asked at Google/Amazon/Meta?
Longest Increasing Path in a Matrix frequently appears in interviews at companies like Google, Amazon, and Meta because it tests DFS, dynamic programming, and graph modeling. Candidates must recognize overlapping subproblems and optimize recursion with memoization.
What data structure is used in Longest Increasing Path in a Matrix?
The main structures are a 2D memoization array for dynamic programming and recursion or a queue for BFS. The matrix itself can be interpreted as a directed graph where edges go from smaller values to larger neighbors.
What is the time complexity of Longest Increasing Path in a Matrix?
The optimal solutions run in O(m*n) time where m and n are the matrix dimensions. With DFS and memoization, each cell's result is computed once and reused. Every DFS checks at most four neighbors, keeping the total work linear in the number of cells.

Ready to solve this problem?

Practice Longest Increasing Path in a Matrix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Increasing Paths in a Grid