Longest Increasing Path in a Matrix

Longest Increasing Path in a Matrix

What is this problem about?

The Longest Increasing Path in a Matrix is a famous problem where you are given a 2D grid of integers. Your goal is to find the length of the longest path where each subsequent cell's value is strictly greater than the previous cell's value. You can move up, down, left, or right, but you cannot move diagonally, and you cannot wrap around the edges of the matrix.

Why is this asked in interviews?

This is a flagship Hard-level problem asked by companies like Google, Meta, and Uber. It acts as the ultimate test of a candidate's ability to combine Depth-First Search (DFS) with Memoization (Dynamic Programming). A naive DFS will recalculate the same paths repeatedly, resulting in an exponential $O(4^{N \times M})$ time limit failure. Interviewers want to see if you can cache results to drastically optimize grid traversal down to $O(N \times M)$.

Algorithmic pattern used

The definitive pattern is DFS with Memoization (also known as Top-Down Dynamic Programming). You create a 2D cache matrix of the same size as the input, initialized with zeros. You loop through every cell in the grid and initiate a DFS. During the DFS, if you attempt to explore a cell that already has a non-zero value in the cache, you immediately return that cached value instead of exploring it again.

Example explanation

Consider the matrix:

9 9 4
6 6 8
2 1 1

We iterate and run DFS from each cell.

• Start at 1 (bottom right). It can't go anywhere strictly increasing. Path length = 1. Cache it.
• Start at 1 (bottom middle). It can go right to 1? No, must be strictly greater. It can go up to 6 or left to 2.
• Let's trace the path from 1 (bottom middle) -> 2 -> 6 -> 9. Length is 4. We save cache[2][1] = 4.
• Now, when we iterate our main loop and eventually call DFS starting on the 2 (bottom left), it looks at 6. The 6 will look at 9. But wait! 6 already explored this and cached its max path. The DFS simply grabs the cached value and adds 1.

Common mistakes candidates make

A very common mistake is trying to keep a visited array (like in standard island-finding algorithms) and un-marking it during backtracking. Because the path must be strictly increasing, it is impossible to loop back onto your own path! Therefore, a visited set is entirely unnecessary and just wastes memory and compute time. The memoization cache itself acts as your history.

Interview preparation tip

To crush the Longest Increasing Path in a Matrix interview question, memorize the structure of a recursive DFS function that returns an integer. Your base case is hitting the edge of the matrix or a cell that isn't strictly greater. Before returning your calculated maximum from the 4 directions, assign it to your cache. This Top-Down DP pattern is universally applicable to many grid-based optimization problems.