Bouncing Diagonal Weights
Hudson River Trading● MediumFULLTIMEOAProblem statement
You are given a square integer matrix of size n by n. A bouncing diagonal begins at a cell of the leftmost column and moves one row up and one column right at each step. If its next step would pass above the top row, it changes its vertical direction and continues down-right. Stop after including the cell in the rightmost column.
The weight of a starting cell is the sum of all entries on its path, including the starting and ending cells.
Return the values in the leftmost column sorted by ascending weight. Break equal-weight ties by ascending starting value. Return values, not row indices or weights.
Function
bouncingDiagonalWeights(matrix: int[][]) → int[]Examples
Example 1
matrix = [[2,3,2],[0,2,5],[1,0,1]]return = [1,2,0]The starting values 2, 0, and 1 have weights 2 + 2 + 1 = 5, 0 + 3 + 5 = 8, and 1 + 2 + 2 = 5. The tie at weight 5 is resolved by value, giving [1,2,0].
Example 2
matrix = [[-4]]return = [-4]The only cell is already in the rightmost column, so its path contains only itself.
Constraints
1 <= n <= 300matrix.length == nand every row has lengthn.-10^6 <= matrix[i][j] <= 10^6