FastPrep

Description

Solutions

Bounding Diagonal Weights

🤘 INTERN📚RELATED PROBLEMS

To veiw the original problem statement, pls check the source image below 🐘

Imagine you have a square grid of numbers, and this grid is n x n in size. Now, let's talk about something called a "bouncing diagonal." Here's how it works:

Starting Point: Imagine you pick a starting point from the leftmost column of the grid. From that point, you draw a diagonal line moving upwards and to the right.

Bouncing Effect: If your diagonal line hits the top edge of the grid, it doesn't stop—it "bounces" downwards and continues moving diagonally to the right again. The diagonal keeps bouncing off the top edge until it reaches the rightmost column of the grid.

Calculating Weight: For each starting point in the leftmost column, you want to calculate its "weight." The weight is simply the sum of all the numbers you encounter as you trace along this bouncing diagonal from that starting point.

🌷༊·˚Credit to ꒰აCharlotte໒꒱ 🧡

Example 1:

Input:  matrix = [[2, 3, 2], [0, 2, 5], [1, 0, 1]]
Output: [1, 2, 0] 
Explanation:
When traversing:

- Starting from matrix[0][0] (which is 2), the diagonal sum is 2 + 1 + 1 = 5. So, you create a pair: Pair(5, 2).

- Starting from matrix[1][0] (which is 0), the diagonal sum is 0 + 3 + 2 = 5. You create another pair: Pair (5, 0).

- Starting from matrix[2][0] (which is 1), the diagonal sum is 1 + 0 + 2 = 3. You create another pair: Pair (3, 1).

So your list pathSums would look like:

pathSums = [Pair(5, 2), Pair(5, 0), Pair (3, 1)]

After sorting pathSum by pathSum:

pathSums = [Pair(3, 1), Pair(5, 2), Pair(5, 0)]

The result would give you the values in the leftmost column [1, 2, 0] in order of increasing diagonal.

Example 2:

Input:  matrix = [[1, 3, 2, 5], [3, 2, 5, 0], [9, 0, 1, 3], [6, 1, 0, 8]]
Output: [1, 3, 9, 6] 
Explanation:
      🐳 Wasn't able to get access to the video explanation, following explanation is an educated guess. If you find anything wrong, feel free to lmk! Many thanks in advance! 
      
      For the given matrix, the weights of the cells in the leftmost column are calculated as follows:
      
      
        The weight of the first cell is the sum of the elements in its bouncing diagonal: 1 + 2 + 5 + 0 = 8.
        The weight of the second cell is the sum of the elements in its bouncing diagonal: 3 + 0 + 0 + 1 = 4.
        The weight of the third cell is the sum of the elements in its bouncing diagonal: 9 + 3 + 2 + 1 = 15.
        The weight of the fourth cell is the sum of the elements in its bouncing diagonal: 1 + 0 + 5 + 0 = 6.
      
      
      The weights are [8, 4, 15, 6], but since we need to sort them by their values in descending order, the final output is [1, 3, 9, 6].

Constraints:

🐾