Quick Overview

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.

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.

Hints

  1. DFS with memoization turns overlapping path searches into one result per cell.

Loading coding console...