Find the longest increasing path in a matrix.
Given an m x n integers matrix, return the length of the longest strictly increasing path in the matrix. From each cell, you can either move in four directions: left, right, up, or down.
Input: matrix = [[1,2],[3,4]]
Output: 3
Explanation: The longest strictly increasing path is 1 - 3 - 4 (or 1 - 2 - 4), both of which have a length of 3.

Question

Find the longest increasing path in a matrix.

Given an m x n integers matrix, return the length of the longest strictly increasing path in the matrix. From each cell, you can either move in four directions: left, right, up, or down.

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

Output: 3

Explanation: The longest strictly increasing path is 1 -> 3 -> 4 (or 1 -> 2 -> 4), both of which have a length of 3.

Anonymous · Accepted Answer

bfs using dynamic programming. Start with an empty dictionary and queue all
locations on the board. 3 each spot gets assigned the max of dp(left), dp(right)
dp(down) dp (up) + 1 for all where up, down, left, and right respectively are
strictly greater (otherwise automatically set to 0). if the spot is not in the
dictionary, add it to queue. empty the queue gradually and if the value is
already in the dictionary, just skip.

Find the longest increasing path in a matrix.

Practice this question with AI

Go Premium

Community Answers

Unlock Full Access

Practice More Questions