Longest Increasing Path In a Matrix

January 10, 2025

Longest Increasing Path In a Matrix

In many real-world problems, navigating through grids and finding optimal paths is a common challenge. One interesting variation of this problem involves finding the longest strictly increasing path within a 2D grid of integers. In this scenario, each cell in the grid contains a non-negative integer, and the objective is to traverse from one cell to another in a way that the values of the cells strictly increase as you move.

The movement is constrained to adjacent cells, either horizontally or vertically, but diagonal moves are not allowed. This problem requires an efficient approach to determine the longest path, making it a compelling topic in the realm of algorithm design and optimization.

Problem:

You are provided with a 2D grid of non-negative integers. Your goal is to determine the length of the longest path in the grid where the values of the cells strictly increase as you move from one cell to the next.

You can move from a cell to its adjacent cells either horizontally or vertically, but diagonal movement is not allowed.

Problem Breakdown

Input: 2D grid of non-negative integers.
Objective: Find the length of the longest strictly increasing path.
Movement: Can move to adjacent cells (up, down, left, right) but not diagonally.
Constraints: Each move must go to a cell with a strictly greater value.
Goal: Determine the longest path by efficiently exploring the grid.

Example 1

Input: matrix = [[5,5,3],[2,3,6],[1,1,1]]

Output: 4

Explanation: The longest increasing path is [1, 2, 3, 6] or [1, 2, 3, 5].

Example 2

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

Output: 7

Explanation: The longest increasing path is [1, 2, 3, 4, 5, 6, 7].

Constraints

1 <= matrix.length, matrix[i].length <= 100

There are mainly three approach to solve this problem –

Recursion
Dynamic Programming (Top-Down)
Dynamic Programming (Bottom-up)

1. Recursion

Time complexity:
Space complexity:

Python

C++

Java

JavaScript

Python

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

        def dfs(r, c, prevVal):
            if (min(r, c) < 0 or r >= ROWS or 
                c >= COLS or matrix[r][c] <= prevVal
            ):
                return 0
            
            res = 1
            for d in directions:
                res = max(res, 1 + dfs(r + d[0], c + d[1], matrix[r][c]))
            return res

        LIP = 0
        for r in range(ROWS):
            for c in range(COLS):
                LIP = max(LIP, dfs(r, c, float('-inf')))
        return LIP

C++

class Solution {
public:
    vector> directions = {{-1, 0}, {1, 0}, 
                                      {0, -1}, {0, 1}};
    
    int dfs(vector>& matrix, int r, int c, int prevVal) {
        int ROWS = matrix.size(), COLS = matrix[0].size();
        if (r < 0 || r >= ROWS || c < 0 || 
            c >= COLS || matrix[r][c] <= prevVal)
            return 0;
        
        int res = 1;
        for (auto d : directions)
            res = max(res, 1 + dfs(matrix, r + d[0], 
                                   c + d[1], matrix[r][c]));
        return res;
    }

    int longestIncreasingPath(vector>& matrix) {
        int ROWS = matrix.size(), COLS = matrix[0].size(), LIP = 0;
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                LIP = max(LIP, dfs(matrix, r, c, INT_MIN));
            }
        }
        return LIP;
    }
};

Java

public class Solution {
    int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    private int dfs(int[][] matrix, int r, int c, int prevVal) {
        int ROWS = matrix.length, COLS = matrix[0].length;
        if (r < 0 || r >= ROWS || c < 0 || 
            c >= COLS || matrix[r][c] <= prevVal) {
            return 0;
        }

        int res = 1;
        for (int[] d : directions) {
            res = Math.max(res, 1 + dfs(matrix, r + d[0], 
                                    c + d[1], matrix[r][c]));
        }
        return res;
    }

    public int longestIncreasingPath(int[][] matrix) {
        int ROWS = matrix.length, COLS = matrix[0].length;
        int LIP = 0;
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                LIP = Math.max(LIP, dfs(matrix, r, c, Integer.MIN_VALUE));
            }
        }
        return LIP;
    }
}

JavaScript

class Solution {
    /**
     * @param {number[][]} matrix
     * @return {number}
     */
    longestIncreasingPath(matrix) {
        const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        const ROWS = matrix.length, COLS = matrix[0].length;

        const dfs = (r, c, prevVal) => {
            if (r < 0 || r >= ROWS || c < 0 || 
                c >= COLS || matrix[r][c] <= prevVal) {
                return 0;
            }

            let res = 1;
            for (let d of directions) {
                res = Math.max(res, 1 + dfs(r + d[0], 
                                        c + d[1], matrix[r][c]));
            }
            return res;
        };

        let LIP = 0;
        for (let r = 0; r < ROWS; r++) {
            for (let c = 0; c < COLS; c++) {
                LIP = Math.max(LIP, dfs(r, c, -Infinity));
            }
        }
        return LIP;
    }
}

2. Dynamic Programming (Top-Down)

Time & Space Complexity

Time complexity:
Space complexity:

Python

Java

C++

JavaScript

Python

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        dp = {}  # (r, c) -> LIP

        def dfs(r, c, prevVal):
            if (r < 0 or r == ROWS or c < 0 or 
                c == COLS or matrix[r][c] <= prevVal
            ):
                return 0
            if (r, c) in dp:
                return dp[(r, c)]

            res = 1
            res = max(res, 1 + dfs(r + 1, c, matrix[r][c]))
            res = max(res, 1 + dfs(r - 1, c, matrix[r][c]))
            res = max(res, 1 + dfs(r, c + 1, matrix[r][c]))
            res = max(res, 1 + dfs(r, c - 1, matrix[r][c]))
            dp[(r, c)] = res
            return res

        for r in range(ROWS):
            for c in range(COLS):
                dfs(r, c, -1)
        return max(dp.values())

Java

public class Solution {
    int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int[][] dp;

    private int dfs(int[][] matrix, int r, int c, int prevVal) {
        int ROWS = matrix.length, COLS = matrix[0].length;
        if (r < 0 || r >= ROWS || c < 0 || 
            c >= COLS || matrix[r][c] <= prevVal) {
            return 0;
        }
        if (dp[r][c] != -1) return dp[r][c];

        int res = 1;
        for (int[] d : directions) {
            res = Math.max(res, 1 + dfs(matrix, r + d[0], 
                                    c + d[1], matrix[r][c]));
        }
        return dp[r][c] = res;
    }

    public int longestIncreasingPath(int[][] matrix) {
        int ROWS = matrix.length, COLS = matrix[0].length;
        int LIP = 0;
        dp = new int[ROWS][COLS];
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                dp[i][j] = -1;
            }
        }
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                LIP = Math.max(LIP, dfs(matrix, r, c, Integer.MIN_VALUE));
            }
        }
        return LIP;
    }
}

C++

class Solution {
public:
    vector> directions = {{-1, 0}, {1, 0}, 
                                      {0, -1}, {0, 1}};
    vector> dp;

    int dfs(vector>& matrix, int r, int c, int prevVal) {
        int ROWS = matrix.size(), COLS = matrix[0].size();
        if (r < 0 || r >= ROWS || c < 0 || 
            c >= COLS || matrix[r][c] <= prevVal) {
            return 0;
        }
        if (dp[r][c] != -1) return dp[r][c];

        int res = 1;
        for (vector d : directions) {
            res = max(res, 1 + dfs(matrix, r + d[0], 
                               c + d[1], matrix[r][c]));
        }
        dp[r][c] = res;
        return res;
    }

    int longestIncreasingPath(vector>& matrix) {
        int ROWS = matrix.size(), COLS = matrix[0].size();
        dp = vector>(ROWS, vector(COLS, -1));
        int LIP = 0;

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                LIP = max(LIP, dfs(matrix, r, c, INT_MIN));
            }
        }
        return LIP;
    }
};

JavaScript

class Solution {
    /**
     * @param {number[][]} matrix
     * @return {number}
     */
    longestIncreasingPath(matrix) {
        const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        const ROWS = matrix.length, COLS = matrix[0].length;
        let dp = Array.from({ length: ROWS }, () => 
                 Array(COLS).fill(-1));

        const dfs = (r, c, prevVal) => {
            if (r < 0 || r >= ROWS || c < 0 || 
                c >= COLS || matrix[r][c] <= prevVal) {
                return 0;
            }
            if (dp[r][c] !== -1) return dp[r][c];

            let res = 1;
            for (let d of directions) {
                res = Math.max(res, 1 + dfs(r + d[0], 
                                        c + d[1], matrix[r][c]));
            }
            dp[r][c] = res;
            return res;
        };

        let LIP = 0;
        for (let r = 0; r < ROWS; r++) {
            for (let c = 0; c < COLS; c++) {
                LIP = Math.max(LIP, dfs(r, c, -Infinity));
            }
        }
        return LIP;
    }
}

3. Dynamic Programming (Bottom-Up)

Time & Space Complexity

Time complexity:
Space complexity:

Python

Java

C++

JavaScript

Python

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        indegree = [[0] * COLS for _ in range(ROWS)]
        
        for r in range(ROWS):
            for c in range(COLS):
                for d in directions:
                    nr, nc = d[0] + r, d[1] + c
                    if (0 <= nr < ROWS and 0 <= nc < COLS and 
                        matrix[nr][nc] < matrix[r][c]
                    ):
                        indegree[r][c] += 1

        q = deque()
        for r in range(ROWS):
            for c in range(COLS):
                if indegree[r][c] == 0:
                    q.append([r, c])

        LIS = 0
        while q:
            for _ in range(len(q)):
                r, c = q.popleft()
                for d in directions:
                    nr, nc = r + d[0], c + d[1]
                    if (0 <= nr < ROWS and 0 <= nc < COLS and 
                        matrix[nr][nc] > matrix[r][c]
                    ):
                        indegree[nr][nc] -= 1
                        if indegree[nr][nc] == 0:
                            q.append([nr, nc])
            LIS += 1
        return LIS

Java

public class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        int ROWS = matrix.length, COLS = matrix[0].length;
        int[][] indegree = new int[ROWS][COLS];
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int r = 0; r < ROWS; ++r) {
            for (int c = 0; c < COLS; ++c) {
                for (int[] d : directions) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < ROWS && nc >= 0 && 
                        nc < COLS && matrix[nr][nc] < matrix[r][c]) {
                        indegree[r][c]++;
                    }
                }
            }
        }

        Queue q = new LinkedList<>();
        for (int r = 0; r < ROWS; ++r) {
            for (int c = 0; c < COLS; ++c) {
                if (indegree[r][c] == 0) {
                    q.offer(new int[]{r, c});
                }
            }
        }

        int LIS = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                int[] node = q.poll();
                int r = node[0], c = node[1];
                for (int[] d : directions) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < ROWS && nc >= 0 && 
                        nc < COLS && matrix[nr][nc] > matrix[r][c]) {
                        if (--indegree[nr][nc] == 0) {
                            q.offer(new int[]{nr, nc});
                        }
                    }
                }
            }
            LIS++;
        }
        return LIS;
    }
}

C++

class Solution {
public:
    int longestIncreasingPath(vector>& matrix) {
        int ROWS = matrix.size(), COLS = matrix[0].size();
        vector> indegree(ROWS, vector(COLS, 0));
        vector> directions = {{-1, 0}, {1, 0}, 
                                          {0, -1}, {0, 1}};
        
        for (int r = 0; r < ROWS; ++r) {
            for (int c = 0; c < COLS; ++c) {
                for (auto& d : directions) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < ROWS && nc >= 0 && 
                        nc < COLS && matrix[nr][nc] < matrix[r][c]) {
                        indegree[r][c]++;
                    }
                }
            }
        }
        
        queue> q;
        for (int r = 0; r < ROWS; ++r) {
            for (int c = 0; c < COLS; ++c) {
                if (indegree[r][c] == 0) {
                    q.push({r, c});
                }
            }
        }
        
        int LIS = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                auto [r, c] = q.front();
                q.pop();
                for (auto& d : directions) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < ROWS && nc >= 0 && 
                        nc < COLS && matrix[nr][nc] > matrix[r][c]) {
                        if (--indegree[nr][nc] == 0) {
                            q.push({nr, nc});
                        }
                    }
                }
            }
            LIS++;
        }
        return LIS;
    }
};

JavaScript

class Solution {
    /**
     * @param {number[][]} matrix
     * @return {number}
     */
    longestIncreasingPath(matrix) {
        const ROWS = matrix.length, COLS = matrix[0].length;
        const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        let indegree = Array.from({ length: ROWS }, () => 
                       Array(COLS).fill(0));
        
        for (let r = 0; r < ROWS; r++) {
            for (let c = 0; c < COLS; c++) {
                for (const [dr, dc] of directions) {
                    const nr = r + dr, nc = c + dc;
                    if (nr >= 0 && nr < ROWS && nc >= 0 && 
                        nc < COLS && matrix[nr][nc] < matrix[r][c]) {
                        indegree[r][c]++;
                    }
                }
            }
        }

        let q = new Queue();
        for (let r = 0; r < ROWS; r++) {
            for (let c = 0; c < COLS; c++) {
                if (indegree[r][c] === 0) {
                    q.push([r, c]);
                }
            }
        }

        let LIS = 0;
        while (!q.isEmpty()) {
            const size = q.size();
            for (let i = 0; i < size; i++) {
                const [r, c] = q.pop();
                for (const [dr, dc] of directions) {
                    const nr = r + dr, nc = c + dc;
                    if (nr >= 0 && nr < ROWS && nc >= 0 && 
                        nc < COLS && matrix[nr][nc] > matrix[r][c]) {
                        indegree[nr][nc]--;
                        if (indegree[nr][nc] === 0) {
                            q.push([nr, nc]);
                        }
                    }
                }
            }
            LIS++;
        }
        return LIS;
    }
}