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

Valid Permutations For DI Sequence Problem

LeetCode 903. You are given a string s of length...

Tallest Billboard Problem

LeetCode 956. You are installing a billboard and want it...

Sum Of Subarray Minimums Problem

LeetCode 907. Given an array of integers arr, find the...

Stone Game Problem

LeetCode 877. Alice and Bob play a game with piles...

Split Array With Same Average Problem

LeetCode 805. You are given an integer array nums.

Soup Servings Problem

LeetCode 808. There are two types of soup, type A...