Longest Increasing Path in Matrix

Problem Overview

Draw an arrow from each cell to every neighbor with a strictly larger value.

Intuition

Draw an arrow from each cell to every neighbor with a strictly larger value. Values only go up along arrows, so the arrows can never loop back, and the grid becomes a directed acyclic graph. The longest increasing path is the longest chain of arrows. Peeling that graph in layers finds it without recursion: cells with no smaller neighbor form the first layer, removing them frees the next layer, and the number of layers is the answer.

Algorithm

1For each cell, count how many neighbors are strictly smaller. Queue every cell whose count is 0.
2Process the queue one layer at a time and count the layers.
3For each cell removed, look at every strictly larger neighbor and lower its count.
4When a count reaches 0, every smaller neighbor has been removed, so queue that cell for the next layer.
5Return the number of layers processed.

Example Walkthrough

Input: matrix = [[1,2,9],[5,3,8],[4,6,7]]

1. Cells 1 and 4 have no smaller neighbor, so they form the first layer.
2. Along the longest chain, each later layer frees the next value: 2, then 3, then 6, then 7, then 8, then 9.
3. The path 1, 2, 3, 6, 7, 8, 9 spans seven layers.

Output: 7

Common Pitfalls

• Use strictly larger values. Equal neighbors do not extend an increasing path.
• A recursive search with memoization is also linear, but a long snake shaped path can overflow the stack.
• Count layers, not cells. Many cells can share a layer.
• Searching from every cell without memoization repeats the same work and can take exponential time.

Longest Increasing Path in Matrix.java

Java

// Approach: Treat each cell as a node with an edge to every strictly larger
// neighbor. That graph has no cycles, and the longest increasing path is the
// number of layers in a topological peel. Cells with no smaller neighbor
// form the first layer. Removing a layer lowers the count of smaller
// neighbors for the cells it touches, and cells reaching zero form the next
// layer. The queue is iterative, so a long path cannot overflow the stack.
// Complexity: O(n * m) time, O(n * m) extra space.
class Solution {
    private static final int[] DR = { -1, 1, 0, 0 };
    private static final int[] DC = { 0, 0, -1, 1 };

    public int longIncPath(int[][] matrix, int n, int m) {
        int total = n * m;
        int[] smaller = new int[total];
        int[] queue = new int[total];
        int tail = 0;

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                int v = matrix[r][c];
                int cnt = 0;
                for (int d = 0; d < 4; d++) {
                    int nr = r + DR[d];
                    int nc = c + DC[d];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < m && matrix[nr][nc] < v)
                        cnt++;
                }
                smaller[r * m + c] = cnt;
                if (cnt == 0)
                    queue[tail++] = r * m + c;
            }
        }

        int head = 0;
        int layers = 0;
        while (head < tail) {
            layers++;
            int end = tail;
            while (head < end) {
                int cell = queue[head++];
                int r = cell / m;
                int c = cell % m;
                int v = matrix[r][c];
                for (int d = 0; d < 4; d++) {
                    int nr = r + DR[d];
                    int nc = c + DC[d];
                    if (nr < 0 || nr >= n || nc < 0 || nc >= m || matrix[nr][nc] <= v)
                        continue;
                    int id = nr * m + nc;
                    if (--smaller[id] == 0)
                        queue[tail++] = id;
                }
            }
        }
        return layers;
    }
}

Was this solution helpful?