Bouncing Diagonal Weights
TikTok● MediumNEW GRADOAProblem statement
You are given a square integer matrix matrix of size n × n. A bouncing diagonal starts at a cell in the leftmost column and initially moves one row up and one column right at each step. When the next upward step would leave the top edge, reverse the vertical direction and continue down-right. Stop after including the cell in the rightmost column.
The weight of a starting cell is the sum of all values on its bouncing diagonal, including the starting and ending cells. For each row, compute the weight of its leftmost cell.
Return the values from the leftmost column sorted first by increasing weight, then by increasing cell value when weights tie. Preserve repeated values; return one value for every starting row.
A path visits exactly one cell in each column. Starting on the top row means its first movement is down-right. For a one-cell matrix, its only cell is the complete path. In a square matrix, a path cannot hit the bottom edge before it has reached the final column.
Function
sortBouncingDiagonals(matrix: int[][]) → int[]Examples
Example 1
matrix = [[1,8,4,3,4],[2,8,0,3,1],[0,7,9,0,8],[5,0,3,1,6],[1,5,0,3,1]]return = [2,5,1,1,0]The five starting rows have weights [20,16,23,16,17]. For example, the path from row 1 visits rows [1,0,1,2,3] and has weight 2+8+0+0+6=16. Rows 1 and 3 tie at weight 16, so their values 2 and 5 appear in that order. The two starting values equal to 1 both remain in the output.
Example 2
matrix = [[5,9],[1,5]]return = [1,5]Both paths have weight 10: 5+5 and 1+9. Sorting the tied starting values gives [1,5].
Constraints
- For this practice version, assume
1 <= n <= 50and every row has exactlynentries. - For this practice version, assume
-10^9 <= matrix[r][c] <= 10^9. - Use a 64-bit integer for weights; returned values still fit in a 32-bit integer.