Longest Increasing Path In A Matrix Problem


Description

LeetCode Problem 329.

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 (i.e., wrap-around is not allowed).

Example 1:

1
2
3
Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

1
2
3
Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3:

1
2
Input: matrix = [[1]]
Output: 1

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • 0 <= matrix[i][j] <= 2^31 - 1


Sample C++ Code

Dynamic programming approach:

  • The 2D array dp[i][j] represents the length of longest increasing path starting from (i, j).
  • For (i, j) neighbor (i’, j’), if matrix[i’][j’] > matrix[i][j] and dp[i’][j’] has been calculated, then calculate dp[i][j] recursively.
  • After all dp[i][j] have been calculated, find the maximum dp[i][j].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        if (!rows) return 0;
        int cols = matrix[0].size();
        
        vector<vector<int>> dp(rows, vector<int>(cols, 0));
        std::function<int(int, int)> dfs = [&] (int x, int y) {
            if (dp[x][y]) return dp[x][y];
            vector<vector<int>> dirs = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
            for (auto &dir : dirs) {
                int xx = x + dir[0], yy = y + dir[1];
                if (xx < 0 || xx >= rows || yy < 0 || yy >= cols) continue;
                if (matrix[xx][yy] <= matrix[x][y]) continue;
                dp[x][y] = std::max(dp[x][y], dfs(xx, yy));
            }
            return ++dp[x][y];
        };
        
        int ret = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                ret = std::max(ret, dfs(i, j));
            }
        }
        
        return ret;
    }
};




Related Posts

Palindromic Substrings Problem

LeetCode 647. Given a string s, return the number of...

Largest Plus Sign Problem

LeetCode 764. You are given an integer n. You have...

K Inverse Pairs Array Problem

LeetCode 629. For an integer array nums, an inverse pair...

Domino And Tromino Tiling Problem

LeetCode 790. You have two types of tiles, a 2...

Decode Ways II Problem

LeetCode 639. A message containing letters from A-Z can be...