A trail runner trains on a height map heights. From a cell she may step to one of its four neighbours (up, down, left, right) only if that neighbour is strictly higher. She may start anywhere. Return the number of cells on the longest possible trail.
Examples
Input: heights = [[3, 4, 5],
[2, 9, 6],
[1, 8, 7]]
Output: 9
Explanation: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 spirals into the centre.
Input: heights = [[5, 5],
[5, 5]]
Output: 1
Constraints
1 <= rows, cols <= 1000 <= heights[i][j] <= 10**6- Exploring every trail separately is exponential; aim for about O(rows * cols * log(rows * cols)).
Goals
- Recognise that strictly increasing moves form an acyclic structure
- Process cells in an order where every successor is already solved