Compute longest increasing path in matrix
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You are given an `m x n` grid (matrix) of integers `grid`, where `m >= 1` and `n >= 1`.
A **path** in the matrix is a sequence of cells where:
- You may move from a cell only to one of its 4 neighbors: up, down, left, or right (no diagonals).
- Each step must go to a cell with a **strictly larger** value than the current cell.
The length of a path is the number of cells in the path.
**Task**
Return the length of the **longest** strictly increasing path that can be found in the matrix.
You may start the path at any cell.
**Example**
For example, given:
- `grid = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]`
One of the longest increasing paths is `1 → 2 → 6 → 9`, so the answer is `4`.
**Constraints**
- `1 <= m, n <= 200`
- `-10^9 <= grid[i][j] <= 10^9`
Your solution should be efficient enough to handle the largest inputs within typical interview time limits.
Quick Answer: This question evaluates algorithmic problem-solving skills in graph traversal and dynamic programming on matrices, measuring understanding of state representation and performance trade-offs in grid-based searches within the Coding & Algorithms domain.
Return the length of the longest path moving 4-directionally to strictly larger values.
Constraints
- grid is non-empty
Examples
Input: ([[9, 9, 4], [6, 6, 8], [2, 1, 1]],)
Expected Output: 4
Explanation: Prompt example.
Input: ([[1]],)
Expected Output: 1
Explanation: Single cell.
Input: ([[3, 4, 5], [3, 2, 6], [2, 2, 1]],)
Expected Output: 4
Explanation: Path 3-4-5-6.
Hints
- DFS with memoization turns overlapping path searches into one result per cell.