Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input is a grid of numbers. From any cell, a path may move only up, down, left, or right, and each move must go to a strictly larger value. The task is to return the maximum number of cells that can appear in any such path.

The key word is strictly. A path can never move from a value to the same value or to a smaller value. That rule gives the problem a hidden structure: every valid move points from a smaller number to a larger number, so valid paths cannot cycle back to where they started.

So the problem is really asking for the longest path in a directed acyclic graph, where every cell is a node and every edge goes from one cell to a larger neighboring cell.

The key insight

Trying every possible path from every cell is too slow because many paths overlap. If two different starts both reach the same cell, the best path starting from that cell is identical in both cases.

That means each cell has a reusable answer:

longest_path_from(row, column)

Once that value is known, any smaller neighbor can use it immediately. This is dynamic programming on a grid, and depth-first search is a natural way to compute the values only when they are needed.

The recurrence is:

best(cell) = 1 + max(best(larger_neighbor))

If a cell has no larger neighbor, its best path length is 1, because the path can include only that cell.

How to derive the optimal solution

Start by asking a smaller question: if the path must start at one specific cell, what is the best answer?

From that cell, there are at most four choices. Any neighbor with a value less than or equal to the current value is invalid. For every valid larger neighbor, the path length is:

1 + best path starting from that neighbor

The best path from the current cell is the maximum of those options. If no larger neighbor exists, the answer is just 1.

Now notice the overlap. A cell’s answer does not depend on how the path reached that cell. It depends only on the matrix values around it. So the algorithm memoizes the result for every cell the first time it is computed.

Then the final answer is:

max(best(row, column) for every cell)

The complexity is:

  • Time: O(m * n) because each cell’s memoized answer is computed once, and each computation checks at most four neighbors
  • Extra space: O(m * n) for the memo table, plus recursion stack space in the worst case

Why memoized DFS works

The strict increase rule is what makes the DFS safe. Every recursive call moves to a larger value, so the search cannot return to an earlier cell on the same path. That removes the main complication of general longest-path problems, which are hard when cycles are allowed.

Memoization then turns the search from exponential to linear. Without it, the same downhill-to-uphill suffix could be recomputed from many starts. With it, the algorithm pays for each cell once and reuses that result everywhere else.

This is also why the algorithm does not need a separate visited set for cycle detection. The values themselves enforce acyclicity. The cache is enough.

Python solution

from functools import lru_cache
import sys
from typing import Iterable, List, Tuple


class Solution:
    _DIRECTIONS: Tuple[Tuple[int, int], ...] = (
        (1, 0),
        (-1, 0),
        (0, 1),
        (0, -1),
    )

    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0

        row_count = len(matrix)
        column_count = len(matrix[0])

        # A worst-case path can touch every cell, so make recursion robust for
        # long thin matrices or carefully constructed increasing grids.
        sys.setrecursionlimit(
            max(sys.getrecursionlimit(), row_count * column_count + 10)
        )

        @lru_cache(maxsize=None)
        def longest_path_from(row: int, column: int) -> int:
            current_value = matrix[row][column]
            best_length = 1

            for next_row, next_column in self._neighbors(
                row,
                column,
                row_count,
                column_count,
            ):
                if matrix[next_row][next_column] <= current_value:
                    continue

                candidate_length = 1 + longest_path_from(next_row, next_column)
                best_length = max(best_length, candidate_length)

            return best_length

        return max(
            longest_path_from(row, column)
            for row in range(row_count)
            for column in range(column_count)
        )

    def _neighbors(
        self,
        row: int,
        column: int,
        row_count: int,
        column_count: int,
    ) -> Iterable[Tuple[int, int]]:
        for row_delta, column_delta in self._DIRECTIONS:
            next_row = row + row_delta
            next_column = column + column_delta

            if 0 <= next_row < row_count and 0 <= next_column < column_count:
                yield next_row, next_column

Interview follow-ups

Can this be solved without recursion?

Yes. Model the matrix as a directed graph where each edge goes from a smaller cell to a larger neighboring cell. Then use topological sorting by layers.

One clean version starts from local maxima: cells that have no larger neighbor. These cells form paths of length 1. Then repeatedly remove them and reduce the outdegree of their smaller neighbors. Each BFS layer represents one more step in the longest increasing path. The number of layers processed is the answer.

This works because all edges point from smaller values to larger values, so the graph is acyclic. The time complexity remains O(m * n), and the extra space remains O(m * n) for degree counts and the queue. The main tradeoff is that the topological version avoids recursion depth risk, but the memoized DFS recurrence is usually easier to derive and explain.

How would you return the actual path instead of only its length?

Store one more piece of information while computing longest_path_from: the next cell that gives the best candidate length.

After every cell’s best length is known, find the cell with the largest value in the memo table. Starting there, follow the stored next-cell pointers until there is no next cell. That reconstructs one optimal path.

The complexity stays O(m * n) time and O(m * n) space. The only practical detail is tie-breaking: if multiple larger neighbors produce the same best length, the implementation should choose a deterministic rule, such as lexicographic cell order, so tests and debugging are predictable.

How would you count the number of longest increasing paths?

Change the DP result for each cell from one value to two values: (best_length, path_count).

For each larger neighbor, compute its best length. If 1 + neighbor_length beats the current best length, replace both the best length and the count. If it ties the current best length, add the neighbor’s count.

After all cells are processed, sum the counts from cells whose best length equals the global maximum. This still works because the strictly increasing rule keeps the graph acyclic. The time complexity remains O(m * n), while the space complexity remains O(m * n). If the count can be huge, the interviewer may ask for results modulo a number such as 1_000_000_007.

What changes if diagonal moves are allowed?

The algorithm barely changes. Replace the four movement directions with eight directions by adding the diagonals.

The same recurrence still applies because the ordering rule is still strictly increasing. There are more candidate neighbors per cell, but the branching factor is still constant. The complexity remains O(m * n) time and O(m * n) space, with a slightly larger constant factor.

What if equal values are allowed in the path?

This changes the problem in an important way. If moves may go to equal values, equal-valued neighboring cells can form cycles. The simple DFS recurrence no longer works by itself because a cell might be able to revisit another cell with the same value.

If the path may not reuse cells, the problem becomes much harder because equal-value regions can behave like general grid path problems. If the intended rule is instead to treat connected equal-value cells as one component, a practical approach is to compress each equal-value connected component into one graph node, then add edges from each component to strictly larger neighboring components. That compressed graph is acyclic, so dynamic programming works again.

The tradeoff is extra preprocessing: component labeling takes O(m * n), and the DP still takes linear time in the number of component edges. The solution is more complex because the interviewer must define exactly how equal-value movement should count toward path length.

Practical takeaway

The shortest path to the solution is to stop seeing the matrix as a collection of independent starts. Each cell has a single reusable answer: the best increasing path that begins there.

Because every valid move goes to a larger value, the graph has no cycles. Memoized DFS computes each cell’s answer once, then the global maximum across all cells is the longest increasing path.