How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Compute longest increasing path in a matrix

Quick Overview

Compute longest increasing path in a matrix evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given an m × n integer matrix, return the length of the longest path of strictly increasing values, where from each cell you may move only up, down, left, or right. Design an efficient algorithm and analyze its time and space complexity. Follow-up: Handle very large matrices where recursion depth could be an issue; provide an iterative or memoized approach that avoids stack overflow.

Quick Answer: Compute longest increasing path in a matrix evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given an m x n integer matrix `matrix`, return the length of the longest path of strictly increasing values. From each cell you may move in four directions: up, down, left, or right. You may NOT move diagonally or move outside the matrix boundary. The path does not need to start or end at any particular cell, and a path of a single cell has length 1. Design an efficient algorithm. A brute-force DFS from every cell re-explores the same sub-paths repeatedly; cache the longest increasing path starting at each cell (memoization / top-down DP) so every cell is computed once. This runs in O(m*n) time and O(m*n) space. Follow-up: For very large matrices where recursion depth could overflow the stack, the same caching idea can be expressed iteratively by processing cells in increasing value order (or via topological order / BFS over the DAG where edges point from smaller to larger neighbors). Example 1: 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: 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: Input: matrix = [[1]] Output: 1

Constraints

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 2^31 - 1

Examples

Input: ([[9,9,4],[6,6,8],[2,1,1]],)

Expected Output: 4

Explanation: Longest increasing path is 1 -> 2 -> 6 -> 9 (length 4).

Input: ([[3,4,5],[3,2,6],[2,2,1]],)

Expected Output: 4

Explanation: Longest increasing path is 3 -> 4 -> 5 -> 6 (length 4); diagonal moves are not allowed.

Input: ([[1]],)

Expected Output: 1

Explanation: A single cell is a path of length 1.

Input: ([[1,2,3,4,5,6,7,8,9]],)

Expected Output: 9

Explanation: The entire strictly increasing row forms one path of length 9.

Input: ([[7,7,7],[7,7,7],[7,7,7]],)

Expected Output: 1

Explanation: All values are equal, so no strictly increasing move is possible; the best path is a single cell.

Input: ([],)

Expected Output: 0

Explanation: An empty matrix has no cells, so the longest path length is 0.

Input: ([[1,2],[4,3]],)

Expected Output: 4

Explanation: Path 1 -> 2 -> 3 -> 4 moves right, down, then left, visiting all four cells.

Hints

Brute-force DFS from every cell recomputes overlapping sub-paths. Notice that the longest increasing path starting at a given cell depends only on that cell — so it can be cached.
Use memoization: dfs(r, c) = 1 + max(dfs(neighbor)) over the four orthogonal neighbors whose value is strictly greater than matrix[r][c]; default to 1 when no larger neighbor exists.
Because edges only point from smaller to larger values, the cells form a DAG (no cycles), so memoization never loops. The answer is the maximum dfs value over all cells.
Follow-up (avoid deep recursion): sort cells by value ascending and relax each cell from its already-processed smaller neighbors, or run a topological/BFS peeling of the DAG — both compute the same DP iteratively with O(1) recursion depth.

Quick Overview