The O(n) Club: Longest Increasing Path in a Matrix — Because Who Needs Diagonals?

The O(n) Club: Longest Increasing Path in a Matrix — Because Who Needs Diagonals?

⚡ TL;DR

Find the longest path in a matrix by moving up, down, left, or right (diagonals are for rebels). Each step must be a strictly higher number. Brute force? Sure, if you’re paid by the millisecond of CPU time. Use DFS with memoization to keep your recruiter happy—and your algorithm faster than your morning espresso.

// Brute force: recursion horror show
int bruteForceLIP(int[][] matrix) {
    // Placeholder: Real code below, this just says DON'T!
    return -1;
}

🧠 How Devs Usually Mess This Up

There’s a bingo card of classic mistakes:

🔍 What’s Actually Going On

Imagine a robot exploring a city made of number-tiled streets. It’s only allowed to walk to adjacent buildings that are taller than the one it’s on, and it leaves a post-it note with the longest possible voyage from each rooftop (memoization—which, as your interviewer will note, is the glue holding this city of code together). DFS explores options from every spot; memoization saves us from exploring dead ends multiple times. We want the single lengthiest journey possible—not the prettiest, not the steepest, just the longest, strictly increasing parade of tiles.

🛠️ PseudoCode

• Prep a 2D memo table to remember results for each cell.
  

  int[][] memo = new int[rows][cols];

• DFS from every cell: Four directions only. Jump only if the neighbor is strictly higher.
  

  int dfs(int r, int c) {
      if (memo[r][c] != 0) return memo[r][c]; // Already solved
      int best = 1;
      for (each direction) {
          if (neighbor is in bounds & neighbor > current) {
              best = Math.max(best, 1 + dfs(nr, nc));
          }
      }
      memo[r][c] = best;
      return best;
  }

• Try all cells as starting points and track the global max.
  

  for (int r = 0; r < rows; r++)
    for (int c = 0; c < cols; c++)
      answer = Math.max(answer, dfs(r, c));

💻 The Code

// DFS, memoization, and absolutely zero diagonals
public class Solution {
    private static final int[][] DIRS = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int rows = matrix.length, cols = matrix[0].length, max = 0;
        int[][] memo = new int[rows][cols];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                max = Math.max(max, dfs(matrix, r, c, memo));
            }
        }
        return max;
    }
    private int dfs(int[][] mat, int r, int c, int[][] memo) {
        if (memo[r][c] != 0) return memo[r][c];
        int best = 1;
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < mat.length && nc >= 0 && nc < mat[0].length
                && mat[nr][nc] > mat[r][c]) {
                best = Math.max(best, 1 + dfs(mat, nr, nc, memo));
            }
        }
        return memo[r][c] = best;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Including diagonals: If you do this, at least don’t put it on your resume.
• Forgetting memoization: Ouch. Without it, you’ll get an exponential runtime and (bonus!) discover every way recursion can make you cry.
• Uninitialized matrices: Always check input. Null arrays are interview poison.
• Edge cases: Single cell? Empty input? Handle both or enjoy some choice exceptions.
• Complexity: Time is O(m*n), space is O(m*n) for memo. No chest-thumping, just facts.

🧠 Interviewer Brain-Tattoo

If you only remember one thing: “DFS with memoization is the Swiss Army knife of matrix problems—deploy it, and everything magically works (unless you go diagonal).”