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:

1. Explore all 4 directions
2. Move only if next cell is greater
3. Take maximum path among all valid moves
4. 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:

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 👇