One of the most common mistakes while solving graph problems on matrices is accidentally turning an O(m*n) problem into exponential recursion 😅
This problem is a perfect example of how DFS + Memoization can optimize brute force beautifully.
📌 Problem Statement
Given an m x n matrix, find the length of the longest increasing path.
You can move only in 4 directions:
- ⬆️ Up
- ⬇️ Down
- ⬅️ Left
- ➡️ Right
Diagonal movement is NOT allowed.
🧠 Example
Input:
[
[9,9,4],
[6,6,8],
[2,1,1]
]
Output: 4
Longest increasing path:
1 → 2 → 6 → 9
❌ Brute Force Idea
For every cell:
- Start DFS
- Try all 4 directions
- Find longest increasing path
Problem?
We repeatedly calculate the same paths again and again.
This causes:
Exponential Time Complexity 😭
✅ Optimization: Memoization (DP)
Instead of recalculating:
Store the answer for each cell.
dp[i][j] = longest increasing path starting from (i, j)
So once computed, we directly reuse it.
🔥 Key Observation
If we already know:
Longest path from (x2, y2) = 5
Then:
Longest path from (x, y) = 1 + 5
No need to compute again.
📌 DFS Flow
For every cell:
- Explore all 4 directions
- Move only if next cell is greater
- Take maximum path among all valid moves
- Store result in DP
✅ Java Solution
class Solution {
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
public int longestIncreasingPath(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
int res = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
res = Math.max(res, dfs(matrix, i, j, dp));
}
}
return res;
}
public int dfs(int[][] matrix, int x, int y, int[][] dp) {
if(dp[x][y] != 0) {
return dp[x][y];
}
dp[x][y] = 1;
for(int i = 0; i < 4; i++) {
int x2 = x + dx[i];
int y2 = y + dy[i];
if(isValid(matrix, x, y, x2, y2)) {
dp[x][y] = Math.max(dp[x][y], 1 + dfs(matrix, x2, y2, dp)
);
}
}
return dp[x][y];
}
public boolean isValid(int[][] matrix, int x, int y, int x2, int y2) {
int m = matrix.length;
int n = matrix[0].length;
if(x2 < 0 || y2 < 0 || x2 >= m || y2 >= n) {
return false;
}
return matrix[x][y] < matrix[x2][y2];
}
}
🎯 Dry Run
Suppose we start from:
matrix[2][1] = 1
Possible increasing moves:
1 → 2 → 6 → 9
DFS computes:
dp[2][1] = 4
Next time if we visit this cell again:
Directly return 4 from DP ✅
No recomputation.
⏱️ Time Complexity
Without Memoization
Exponential
because we repeatedly explore same paths.
With Memoization
Each cell is computed only once.
Time Complexity: O(m * n)
Why?
- Total cells =
m * n - Each cell explores at most 4 directions
So overall:
O(4 * m * n) = O(m * n)
💾 Space Complexity
DP Array
O(m * n)
Recursion Stack
Worst case increasing path:
O(m * n)
Final Space Complexity
O(m * n)
🧭 Understanding the Direction Arrays
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
These arrays help us move in all 4 valid directions inside the matrix.
Think of it like this:
| Direction | dx | dy |
|---|---|---|
| Up ⬆️ | -1 | 0 |
| Right ➡️ | 0 | 1 |
| Down ⬇️ | 1 | 0 |
| Left ⬅️ | 0 | -1 |
Suppose current cell is:
(x, y)
Then:
x2 = x + dx[i]
y2 = y + dy[i]
generates the next position.
🔍 Example
Current cell:
(2, 3)
1️⃣ Up
dx = -1
dy = 0
New position:
(2 - 1, 3 + 0)
= (1, 3)
Move upward ⬆️
2️⃣ Right
dx = 0
dy = 1
New position:
(2, 4)
Move right ➡️
3️⃣ Down
dx = 1
dy = 0
New position:
(3, 3)
Move downward ⬇️
4️⃣ Left
dx = 0
dy = -1
New position:
(2, 2)
Move left ⬅️
This is a very common matrix traversal pattern used in:
- DFS
- BFS
- Flood Fill
- Islands problems
- Graph traversal on grids
- Shortest path problems
🔥 Dry Run
Matrix:
[
[9, 9, 4],
[6, 6, 8],
[2, 1, 1]
]
We start DFS from:
matrix[2][1] = 1
because smaller numbers usually create longer increasing paths.
Step 1️⃣
Current cell:
(2,1) = 1
Explore all 4 directions.
Up ⬆️
(1,1) = 6
Valid because:
6 > 1
So:
1 → 6
Now recursively call DFS on (1,1).
Step 2️⃣
Current cell:
(1,1) = 6
Explore directions.
Up ⬆️
(0,1) = 9
Valid because:
9 > 6
Path becomes:
1 → 6 → 9
DFS on (0,1).
Step 3️⃣
Current cell:
(0,1) = 9
No adjacent greater value exists.
So:
dp[0][1] = 1
Return back.
Step 4️⃣
Back to:
(1,1) = 6
We now know:
Longest path from 9 = 1
So:
dp[1][1] = 1 + 1 = 2
Return back.
Step 5️⃣
Back to:
(2,1) = 1
Current best:
1 → 6 → 9
Length = 3
But continue exploring other directions.
Left ⬅️
(2,0) = 2
Valid because:
2 > 1
Path:
1 → 2
DFS on (2,0).
Step 6️⃣
Current cell:
(2,0) = 2
Up:
(1,0) = 6
Valid.
Then from 6:
6 → 9
Final path:
1 → 2 → 6 → 9
Length:
4
So:
dp[2][1] = 4
💡 Most Important Optimization
Now suppose another DFS again reaches:
(1,0) = 6
We already computed:
dp[1][0] = 2
So we directly reuse it instead of recalculating.
That is exactly why memoization makes this solution:
O(m * n)
instead of exponential 🚀
🔥 Important Interview Insights
This problem teaches:
✅ DFS on Matrix
✅ Memoization
✅ DP on Graphs
✅ Avoiding repeated recursion
✅ Converting exponential → linear complexity
⚠️ Common Mistakes
1. Using diagonal directions
Wrong:
{-1,-1}, {-1,1}, {1,-1}, {1,1}
Only 4 directions allowed.
2. Forgetting memoization
Without DP → TLE.
3. Boundary check mistake
Always validate:
x2 and y2
NOT current coordinates.
🚀 Final Thoughts
At first glance, this problem feels like a hard graph DFS problem.
But once you identify:
Overlapping Subproblems
it becomes a very elegant DFS + Memoization problem.
One of my favorite patterns for matrix DFS problems 🔥
💬 What do you think?
- Did you solve it using DFS or Topological Sort?
- Have you seen similar memoization patterns in interviews?
- Which matrix problem should I break down next?
Would love to discuss 👇
Top comments (0)