We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Get Biggest Three Rhombus Sums in a Grid

Difficulty: Medium

Problem Description

You are given an m x n integer matrix grid. A rhombus sum is the sum of the elements that form the border of a regular rhombus shape in grid. The rhombus must have the shape of a square rotated 45 degrees with each of the corners centered in a grid cell. Return the biggest three distinct rhombus sums in the grid in descending order. If there are less than three distinct values, return all of them.

Key Insights

  • The rhombus can vary in size from 0 to the minimum of the horizontal and vertical distance from the center cell.
  • Each rhombus sum can be calculated by iterating through possible sizes and summing the appropriate border elements.
  • The use of a set can help in collecting distinct rhombus sums.
  • Sorting can be applied to extract the three largest distinct sums efficiently.

Space and Time Complexity

Time Complexity: O(m * n * min(m, n)), where m is the number of rows and n is the number of columns in the grid. Each cell can be the center of a rhombus, and for each cell, we calculate the sum for different sizes of rhombus. Space Complexity: O(k), where k is the number of distinct rhombus sums collected.

Solution

To solve the problem, we can iterate through each cell in the grid, treating each cell as the center of a potential rhombus. For each center cell, we can calculate the rhombus sums by expanding outwards in a diamond shape. The sums are collected in a set to ensure distinct values. After calculating all possible rhombus sums, we can sort them and return the largest three. We can use a priority queue to efficiently extract the top three values.

Code Solutions

def getBiggestThree(grid):
    m, n = len(grid), len(grid[0])
    rhombus_sums = set()

    for i in range(m):
        for j in range(n):
            # Add the center cell (area 0 rhombus)
            rhombus_sums.add(grid[i][j])
            # Expand the rhombus
            for size in range(1, min(m, n)):
                current_sum = 0
                for k in range(size + 1):
                    if i + k < m and j - size + k >= 0: 
                        current_sum += grid[i + k][j - size + k]
                    if i + k < m and j + size - k < n: 
                        current_sum += grid[i + k][j + size - k]
                    if k > 0:  # avoid double counting the top point
                        if i - k >= 0 and j - size + k >= 0:
                            current_sum += grid[i - k][j - size + k]
                        if i - k >= 0 and j + size - k < n:
                            current_sum += grid[i - k][j + size - k]
                rhombus_sums.add(current_sum)

    # Get the largest three distinct sums
    return sorted(rhombus_sums, reverse=True)[:3]
← Back to All Questions