Search⌘ K
AI Features

Solution: Longest Increasing Path in a Matrix

Let’s solve the Longest Increasing Path in a Matrix problem using the Dynamic Programming pattern.

Statement

You are given an m×nm × 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==m == matrix.length

  • n==n == ...