Practice/Meta/Leetcode 329. Longest Increasing Path in a Matrix

Leetcode 329. Longest Increasing Path in a Matrix

CodingMust

Problem

You are given an m x n integer matrix. Your task is to find the length of the longest path where each successive cell in the path contains a strictly greater value than the previous cell.

You can move from any cell to its adjacent cells in four directions: up, down, left, or right. However, you cannot move diagonally, and you cannot revisit cells in the same path.

Return the length of the longest strictly increasing path that exists in the matrix.

Requirements

1. Implement a function that accepts a 2D integer matrix as input
2. Find the longest path where values strictly increase
3. Movement is restricted to four cardinal directions (up, down, left, right)
4. A path cannot revisit the same cell
5. Return the length of the longest such path

Constraints

• m == matrix.length (number of rows)
• n == matrix[i].length (number of columns)
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 2^31 - 1
• The path must be strictly increasing (equal values do not count as increasing)

Examples

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]. Starting from 1 at position (2,1), we can move to 2 at (2,0), then to 6 at (1,0), and finally to 9 at (0,0), giving us length 4.

Example 2:

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]] Output: 4 Explanation: One possible longest path is [2,3,4,5].

Example 3:

Input: matrix = [[1]] Output: 1 Explanation: A single cell matrix has a maximum path length of 1.