Problem: Longest Increasing Path in a Matrix

hard

40 min

Explore how to determine the longest strictly increasing path in an integer matrix by applying dynamic programming. Understand movement constraints and practice solving this classic optimization problem to improve your coding interview skills.

Statement

You are given an $m × n$ matrix of integers. Your task is to determine the length of the longest strictly increasing path within the matrix.

A path is defined by consecutively moving from one cell to another adjacent cell. From any cell, movement is allowed only in four directions: up, down, left and right.

Diagonal movement is not allowed. You also cannot move outside the matrix boundaries (no wrap-around).

A path is considered increasing if each subsequent cell contains a strictly greater integer than the previous one.

Your goal is to return the maximum length among all possible increasing paths in the matrix.

Constraints:

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

Problem: Longest Increasing Path in a Matrix

hard

40 min

Statement

You are given an $m × n$ matrix of integers. Your task is to determine the length of the longest strictly increasing path within the matrix.

A path is defined by consecutively moving from one cell to another adjacent cell. From any cell, movement is allowed only in four directions: up, down, left and right.

Diagonal movement is not allowed. You also cannot move outside the matrix boundaries (no wrap-around).

A path is considered increasing if each subsequent cell contains a strictly greater integer than the previous one.

Your goal is to return the maximum length among all possible increasing paths in the matrix.

Constraints:

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

Problem: Longest Increasing Path in a Matrix

Statement

Examples

Understand the problem

Figure it out!

Try it yourself

Problem: Longest Increasing Path in a Matrix

Statement

Examples

Understand the problem

Figure it out!

Try it yourself