Get Biggest Three Rhombus Sums In A Grid - Leetcode Solution

Problem Statement: Given an m x n integer matrix grid, return an array of the top three largest rhombus sum values in grid. The rhombus sum is defined as the sum of the elements that form the border of a regular rhombus shape in grid. The rhombus must have one of the following three sizes:

2k + 1 x 2k + 1, k >= 0 2k + 1 x 2k, k >= 1 2k x 2k + 1, k >= 1

A rhombus is determined by its center position, (r, c), which must be strictly inside the matrix.

First, let's understand the problem statement. Given a matrix, we need to find the top three largest rhombus sums. The rhombus sum is the sum of the elements that form the border of a rhombus shape in the grid. The rhombus shape can have three different sizes, as described in the problem statement. The center position of the rhombus must be strictly inside the matrix.

Now, let's move to the solution of the problem.

Approach:

In order to find the rhombus sum, we need to iterate through all possible rhombus configurations for each cell of the matrix. For a given cell (r, c) in the matrix, we need to consider all possible rhombus sizes, and for each rhombus size, we need to find the sum of the border elements.

There are three types of rhombus shapes that we need to consider:

Type 1: 2k + 1 x 2k + 1, k >= 0 Type 2: 2k + 1 x 2k, k >= 1 Type 3: 2k x 2k + 1, k >= 1

Here, we need to consider all possible values of k for each type of rhombus. For each rhombus, we need to find the sum of its border elements.

To find the sum of the border elements for a given rhombus, we can use the following approach:

• Initialize an empty list to store the border elements of the rhombus.
• For each side of the rhombus, we can iterate through the elements of the matrix along that side and add them to the list.
• The sum of the elements in the list gives us the rhombus sum.

We can optimize this process by precomputing the sum of the elements along each row and column for the matrix. This will allow us to compute the rhombus sum for any rhombus quickly.

To find the top three largest rhombus sums, we can maintain a list of the top three sums found so far. As we iterate through each cell in the matrix, we can update this list with the new largest rhombus sums found.

Algorithm:

1. Initialize an empty list, result, to store the top three largest rhombus sums.
2. Compute the cumulative sum of the elements along each row and column of the matrix.
3. For each cell (r, c) in the matrix: a. For each type of rhombus: i. For each value of k for the current type of rhombus:
   • Compute the sum of the border elements for the current rhombus configuration using the precomputed row and column sums.
   • If the current sum is larger than any of the results in result, update result with the new sum.
4. Return result.

Code:

Let's see the code implementation.

class Solution:
    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
        m, n = len(grid), len(grid[0])
        
        # precompute row sums
        row_sums = [[0] * (n+1) for _ in range(m)]
        for i in range(m):
            for j in range(n):
                row_sums[i][j+1] = row_sums[i][j] + grid[i][j]
        
        # precompute column sums
        col_sums = [[0] * n for _ in range(m+1)]
        for i in range(m):
            for j in range(n):
                col_sums[i+1][j] = col_sums[i][j] + grid[i][j]
                
        def get_borders(r, c, k, row_sums, col_sums):
            borders = []
            if k == 0:
                borders.extend([
                    grid[r][c],
                ])
            else:
                # upper left corner to upper right corner
                borders.extend([
                    row_sums[r-k][c+k] - row_sums[r-k][c-k-1],
                ])
                # upper right corner to lower right corner
                borders.extend([
                    col_sums[r+k][c+k-1] - col_sums[r-k][c+k-1],
                ])
                # lower right corner to lower left corner
                borders.extend([
                    row_sums[r+k][c-k] - row_sums[r+k][c+k],
                ])
                # lower left corner to upper left corner
                borders.extend([
                    col_sums[r-k-1][c-k] - col_sums[r+k-1][c-k],
                ])
            return borders
        
        result = []
        for r in range(m):
            for c in range(n):
                for k in range(min(r, c, m-r-1, n-c-1)+1):
                    # type 1: 2k+1 x 2k+1
                    if k == 0:
                        s = grid[r][c]
                        if s not in result:
                            result.append(s)
                            result.sort(reverse=True)
                            if len(result) > 3:
                                result.pop()
                    # type 2: 2k+1 x 2k
                    else:
                        s = sum(get_borders(r, c, k, row_sums, col_sums))
                        if s not in result:
                            result.append(s)
                            result.sort(reverse=True)
                            if len(result) > 3:
                                result.pop()
                    # type 3: 2k x 2k+1
                    if k != 0 and k < min(r, c, m-r-1, n-c-1):
                        s = sum(get_borders(r, c, k-1, row_sums, col_sums))
                        if s not in result:
                            result.append(s)
                            result.sort(reverse=True)
                            if len(result) > 3:
                                result.pop()
                            
        return result

Time Complexity: The time complexity of the algorithm is O(mnk), where m and n are the dimensions of the matrix and k is the maximum size of the rhombus. Since k is at most min(m, n)/2, the time complexity is O(mn(min(m,n)^2)).

Space Complexity: The space complexity of the algorithm is O(mn) for the row and column sums and O(1) for the result list. Therefore, the total space complexity is O(mn).

1