Longest Increasing Path

Find the longest path in a matrix where each step increases in value. This tests graph traversal and optimization skills, crucial for system design and algorithm efficiency.

graphdfsmemoizationdynamic programmingmatrix

Problem Statement

Given a matrix of integers, find the length of the longest path starting from any cell, where you can only move up, down, left, or right, and the value of the next cell must be strictly greater than the current cell.

Example 1

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]

Output: 4

The longest increasing path is [1, 2, 6, 9]. Therefore, return 4.

Example 2

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]

Output: 4

The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Constraints

-The matrix will have at least one row and one column.
-All integers in the matrix will be unique.
-You can only move up, down, left, or right.
-The value of the next cell must be strictly greater than the current cell.

Brute Force Approach

The brute force approach would be like exploring every possible route from every cell in the matrix. We would start at each cell and recursively explore all possible paths, checking if each adjacent cell has a greater value. This is highly inefficient because we will recompute the same paths multiple times.

TimeO(4^(m*n))

SpaceO(m*n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem