MANG Problem #22: Longest Increasing Path in a Matrix (Hard)

1. 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.

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4 (Path: 1 -> 2 -> 6 -> 9)

2. Approach: DFS + Memoization

A naive DFS from every cell would have exponential time complexity ($4^{MN}$). We optimize this by storing the result of each cell.

State: memo[r][c] stores the longest increasing path starting from cell (r, c).
DFS Function:
- Check the 4 neighbors.
- If a neighbor is within bounds AND matrix[next] > matrix[curr]:
  - Calculate 1 + dfs(next).
- Record the maximum of all valid directions in memo[r][c].
Iterate: Run DFS for every cell in the matrix and update a global maximum.

3. Java Implementation

public int longestIncreasingPath(int[][] matrix) {
    if (matrix == null || matrix.length == 0) return 0;
    int m = matrix.length, n = matrix[0].length;
    int[][] memo = new int[m][n];
    int max = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            max = Math.max(max, dfs(matrix, i, j, memo));
        }
    }
    return max;
}

private int dfs(int[][] matrix, int r, int c, int[][] memo) {
    if (memo[r][c] != 0) return memo[r][c];
    
    int currentMax = 1;
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    
    for (int[] d : dirs) {
        int nr = r + d[0], nc = c + d[1];
        if (nr >= 0 && nr < matrix.length && nc >= 0 && nc < matrix[0].length 
            && matrix[nr][nc] > matrix[r][c]) {
            currentMax = Math.max(currentMax, 1 + dfs(matrix, nr, nc, memo));
        }
    }
    
    memo[r][c] = currentMax;
    return currentMax;
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: This is a Directed Acyclic Graph (DAG) problem in disguise. Because the path must be increasing, you can never go in a circle. Every cell is a node, and every increasing step is a directed edge.
Why Memoization?: If you find that the longest path from (1, 1) is length 5, and then another DFS from (0, 1) arrives at (1, 1), it doesn't need to re-calculate everything. It just takes 1 + 5.
The Base Case: If a cell has no neighbors larger than itself, the longest path is just itself (length 1).

5. Interview Discussion

Interviewer: "What is the time complexity?"
You: "O(M * N) because we calculate the result for each cell exactly once."
Interviewer: "Can we solve this using Topological Sort?"
You: "Yes! We can calculate the in-degree of every cell (how many neighbors are smaller than it). Perform Kahn's algorithm; the number of layers in the BFS is our longest path."