Longest Increasing Path in a Matrix

hard

Acceptance: 42%

GraphsDFSTopological Sort

Given an m-by-n grid of integers, find the length of the longest path of strictly increasing values. From any cell, you may step to any of the four cardinal neighbors (up, down, left, right), but not diagonally and not outside the grid.

Examples

Example 1:

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

Output:9

Explanation: The path 1->2->3->4->5->6->7->8->9 visits every cell in increasing order.

Example 2:

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

Output:6

Explanation: The path 1->2->3->4->5->6 covers all cells.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Longest Increasing Path in a Matrix

Examples

Hints

Related Problems