Longest Decreasing Matrix Path with Limited Relaxations
Duolingo● HardNEW GRADONSITE INTERVIEWProblem statement
Given an integer matrix and a nonnegative integer k, return a longest orthogonal path of cell coordinates.
A move to an up, down, left, or right neighbor is:
- free when the next value is strictly smaller than the current value; or
- a relaxation when the next value is greater than or equal to the current value.
The path may use at most k relaxed moves. Because every cycle contains at least one non-decreasing move, the relaxation budget keeps every valid walk finite; a coordinate may therefore be revisited only after spending additional budget.
Return the coordinates as [row, column] rows. If several paths have maximum length, return the lexicographically smallest coordinate sequence. Setting k = 0 is the original longest-decreasing-path task, while returning coordinates and accepting positive k preserve both reported follow-ups.
Function
longestRelaxedDecreasingPath(matrix: int[][], k: int) → int[][]Examples
Example 1
matrix = [[9,8,7],[2,3,6],[1,4,5]]k = 0return = [[0,0],[0,1],[0,2],[1,2],[2,2],[2,1],[1,1],[1,0],[2,0]]The spiral visits values 9, 8, 7, 6, 5, 4, 3, 2, 1. Every move is strictly decreasing, so no relaxation is used.
Example 2
matrix = [[1,2]]k = 1return = [[0,1],[0,0],[0,1],[0,0]]Start at value 2, move down to 1 for free, spend the one relaxation to return to 2, then move down to 1 again. The repeated coordinates have different remaining-budget states.
Example 3
matrix = [[4,3],[2,1]]k = 0return = [[0,0],[0,1],[1,1]]There are multiple decreasing paths of length three. The returned one is lexicographically smallest.
Constraints
1 <= matrix.length, matrix[0].length <= 20.- All rows have the same length.
-10^9 <= matrix[r][c] <= 10^9.0 <= k <= 5.