329. Max Rising Path

Longest Increasing Path in a Matrix

A must-know matrix DFS pattern. Problem 329 is a classic example.

Goal is to find the longest strictly increasing path in a matrix.

Constraint is that from any cell, when trying to extend a path, only four cardinal directions (east, south, west, north) are allowed — no diagonals.

Of course, stepping outside the matrix is also forbidden, so boundary checks come first.

Scanning Effortlessly

For every element matrix[i][j] in the matrix,

we try using it as a starting point to find the longest increasing path from there.

So we create maxRisingPath, a 2D array with the same dimensions as matrix.

Initially, all elements of maxRisingPath are set to -1, meaning unvisited.

Then for each matrix[i][j], we check its four potential neighbors:

1. matrix[i][j + 1] — east
2. matrix[i + 1][j] — south
3. matrix[i][j - 1] — west
4. matrix[i - 1][j] — north

When checking neighbor $x$, once we confirm $x$ is within bounds,

we then check whether $x$'s value is strictly greater than matrix[i][j].

If so, we look up the longest increasing path starting from $x$.

Adding 1 gives us the longest increasing path from matrix[i][j] going through $x$.

So if neighbor $x$ shows -1 in maxRisingPath,

it means $x$ hasn't been visited yet — we run DFS on $x$ first.

Once $x$'s longest path length is determined, say $k$, we apply:

$maxRisingPath[i][j] = max(maxRisingPath[i][j], 1 + k)$

After updating maxRisingPath[i][j], don't forget to compare it with global maximum.

Both time and space complexity are $O(mn)$, where $m$ and $n$ are number of rows and columns.

Problem 329 is officially labeled hard, but it's actually not difficult. Even relatively easy.

A great problem to build fundamentals.

C++

#include <algorithm>
#include <vector>
using namespace std;

class MaxRisingPath // LeetCode Q.329.
{
private:
    // An entry's max rising path value is -1 if this entry is unsearched.
    // Otherwise, max rising path value is the finalized value w.r.t. entry.
    vector<vector<int>> entries, maxRisingPath;

    int maxRisingLen = 1; // Base case.

    void dfsRisingPath(int rowIdx, int colIdx) {
        maxRisingPath[rowIdx][colIdx] = 1; // Base case: a path of only current entry.

        vector<pair<int, int>> neighbors = {
            {rowIdx + 1, colIdx}, // South.
            {rowIdx - 1, colIdx}, // North.
            {rowIdx, colIdx + 1}, // East.
            {rowIdx, colIdx - 1} // West.
        };

        for (const auto& [neighborRowIdx, neighborColIdx] : neighbors) {
            // Inbound checks on row & col indices.
            if (0 > neighborRowIdx || neighborRowIdx >= entries.size())
                continue;

            if (0 > neighborColIdx || neighborColIdx >= entries[0].size())
                continue;

            // Skip neighbors that aren't bigger than current entry.
            if (entries[rowIdx][colIdx] >= entries[neighborRowIdx][neighborColIdx])
                continue;

            if (maxRisingPath[neighborRowIdx][neighborColIdx] == -1) // Unsearched neighbor.
                dfsRisingPath(neighborRowIdx, neighborColIdx);

            int risingLen = 1 + maxRisingPath[neighborRowIdx][neighborColIdx];

            if (risingLen > maxRisingPath[rowIdx][colIdx])
                maxRisingPath[rowIdx][colIdx] = risingLen;

            if (risingLen > maxRisingLen)
                maxRisingLen = risingLen;
        }
    }

public:
    int findLongestRisingPath(vector<vector<int>>& matrix) {
        entries = matrix;

        maxRisingPath.assign(matrix.begin(), matrix.end()); // Base case.
        for (auto& row : maxRisingPath)
            fill(row.begin(), row.end(), -1);

        for (int rowIdx = 0; rowIdx < matrix.size(); rowIdx++) {
            for (int colIdx = 0; colIdx < matrix[0].size(); colIdx++) {
                if (maxRisingPath[rowIdx][colIdx] == -1)
                    dfsRisingPath(rowIdx, colIdx);
            }
        }

        return maxRisingLen;
    }
};

Python

class MaxRisingPath:  # LeetCode Q.329.
    def __init__(self):
        self.matrix = []
        self.max_rising_path = []
        self.max_rising_len = 1

    def find_longest_rising_path(self, matrix: list[list[int]]) -> int:
        self.matrix = matrix

        # An entry's max rising path value is -1 if this entry is unsearched.
        # Otherwise, max rising path value is the finalized value w.r.t. entry.
        self.max_rising_path = [[-1] * len(matrix[0]) for _ in range(len(matrix))]

        self.max_rising_len = 1  # Base case.

        for row_idx in range(len(matrix)):
            for col_idx in range(len(matrix[0])):
                if self.max_rising_path[row_idx][col_idx] == -1:
                    self._dfs_rising_path(row_idx, col_idx)

        return self.max_rising_len

    def _dfs_rising_path(self, row_idx: int, col_idx: int) -> None:
        self.max_rising_path[row_idx][col_idx] = 1  # Base case: a path of only current entry.

        neighbors: list[tuple[int, int]] = [
            (row_idx + 1, col_idx), (row_idx - 1, col_idx),  # South & North.
            (row_idx, col_idx + 1), (row_idx, col_idx - 1)  # East & West.
        ]

        for neighbor_row_idx, neighbor_col_idx in neighbors:
            # Inbound checks on row & col indices.
            if not (0 <= neighbor_row_idx < len(self.matrix)): continue

            if not (0 <= neighbor_col_idx < len(self.matrix[0])): continue

            # Only consider neighbors that are bigger than current entry.
            if self.matrix[row_idx][col_idx] < self.matrix[neighbor_row_idx][neighbor_col_idx]:
                # Unsearched neighbor.
                if self.max_rising_path[neighbor_row_idx][neighbor_col_idx] == -1:
                    self._dfs_rising_path(neighbor_row_idx, neighbor_col_idx)

                rising_len = 1 + self.max_rising_path[neighbor_row_idx][neighbor_col_idx]

                if rising_len > self.max_rising_path[row_idx][col_idx]:
                    self.max_rising_path[row_idx][col_idx] = rising_len

                if rising_len > self.max_rising_len: self.max_rising_len = rising_len