Introduction
Finding the Longest Increasing Path (LIP) in a matrix is a popular problem in computer science and algorithm design. It combines concepts from dynamic programming, depth-first search (DFS), and graph traversal. This problem is commonly asked in coding interviews and used in real-world applications like pathfinding, data analysis, and game design.
Problem Statement
You are given a 2D matrix of integers. Find the length of the longest increasing path in the matrix.
Rules:
You can move up, down, left, or right.
The next cell must contain a strictly larger number.
No cell can be revisited.
Example:
Matrix:
[ [9, 9, 4],
[6, 6, 8],
[2, 1, 1] ]
Longest Increasing Path: [1 → 2 → 6 → 9]
Length = 4
Expanded Examples
Example 1
Matrix:
[ [1, 2, 3],
[4, 5, 6],
[7, 8, 9] ]
One valid increasing path is 1 → 2 → 3 → 6 → 9. Length = 5.
Example 2
Matrix:
[ [3, 4, 5],
[6, 2, 6],
[2, 2, 1] ]
A valid increasing path is 3 → 4 → 5 → 6. Length = 4.
Approaches to Solve the Problem
1. Brute Force (Naive DFS)
Drawback: Exponential runtime, repeats calculations many times.
2. DFS with Memoization (Top-Down Dynamic Programming)
Each cell’s longest path depends on its larger neighbors.
Use recursion + caching to avoid recalculating.
Store results in a memo table.
Steps:
Initialize a 2D memo table with 0.
For each cell, run DFS to find the longest increasing path.
Store results in memo and reuse them.
Time Complexity: O(M × N)
Space Complexity: O(M × N)
3. Graph-Based (Kahn’s Algorithm, Topological BFS)
Treat each cell as a node.
Add directed edges to neighbors with larger values.
Perform topological BFS (Kahn’s algorithm).
The number of BFS layers = length of longest increasing path.
Pros: Iterative, avoids recursion limits.
Cons: More complex implementation.
Time Complexity: O(M × N)
Space Complexity: O(M × N)
Python Examples
DFS with Memoization
from functools import cache
def longestIncreasingPath(matrix):
if not matrix or not matrix[0]:
return 0
rows, cols = len(matrix), len(matrix[0])
@cache
def dfs(r, c):
best = 0
for dr, dc in [(-1,0),(0,1),(1,0),(0,-1)]:
nr, nc = r+dr, c+dc
if 0<=nr<rows and 0<=nc<cols and matrix[nr][nc] > matrix[r][c]:
best = max(best, dfs(nr,nc))
return best + 1
return max(dfs(r,c) for r in range(rows) for c in range(cols))
# Example
print(longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]])) # Output: 4
Topological BFS (Kahn’s Algorithm)
from collections import deque
def longestIncPathKahn(matrix):
if not matrix or not matrix[0]:
return 0
rows, cols = len(matrix), len(matrix[0])
indeg = [[0]*cols for _ in range(rows)]
dirs = [(-1,0),(0,1),(1,0),(0,-1)]
for r in range(rows):
for c in range(cols):
for dr,dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<rows and 0<=nc<cols and matrix[nr][nc] < matrix[r][c]:
indeg[r][c]+=1
q = deque((r,c) for r in range(rows) for c in range(cols) if indeg[r][c]==0)
length = 0
while q:
length+=1
for _ in range(len(q)):
r,c=q.popleft()
for dr,dc in dirs:
nr,nc=r+dr,c+dc
if 0<=nr<rows and 0<=nc<cols and matrix[nr][nc]>matrix[r][c]:
indeg[nr][nc]-=1
if indeg[nr][nc]==0:
q.append((nr,nc))
return length
Common Mistakes to Avoid
Skipping memoization → exponential runtime.
Forgetting strict inequality (> not >=).
Not adding 1 for the current cell.
Accessing neighbors before checking bounds.
Recursion depth issues on large inputs → prefer BFS.
Real-World Applications
Games: Finding valid paths on maps/terrains.
Data Science: Trend analysis in grid-based datasets.
AI/Robotics: Path planning where conditions increase step by step.
Image Processing: Detecting gradient-based patterns in pixel grids.
Conclusion
The Longest Increasing Path in a Matrix problem can be solved efficiently with DFS + Memoization or a Topological BFS (Kahn’s Algorithm). Both provide O(M × N) solutions and are ideal for interviews and real-world implementations. DFS + Memoization is intuitive, while BFS avoids recursion depth limits.