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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Get Biggest Three Rhombus Sums in a Grid

Number: 1990

Difficulty: Medium

Paid? No

Companies: Uber, Capital One, Quora

Problem Description

Given an m x n integer matrix grid, a rhombus is defined as a square rotated by 45 degrees. Its border is formed by the cells along the four sides of this diamond-shape. Note that a rhombus of area 0 (a single cell) is allowed. The task is to find all distinct rhombus border sums, then return the biggest three in descending order. If there are fewer than three distinct sums, return all of them.

Key Insights

  • Every grid cell is a valid rhombus of area 0.
  • For any potential rhombus of size d > 0 with top vertex (i,j), its other vertices can be computed as:
    • Right vertex: (i+d, j+d)
    • Bottom vertex: (i+2*d, j)
    • Left vertex: (i+d, j-d)
  • A rhombus border sum can be computed by iterating over its four edges; be careful not to double count vertices.
  • The rhombus is valid if it fits entirely within the grid:
    • i + 2*d < m and j + d < n and j - d >= 0.
  • Use a set to track distinct sums and then sort the results in descending order.

Space and Time Complexity

Time Complexity: O(m * n * min(m, n)) in the worst case, where m and n are the dimensions of the grid. Space Complexity: O(m * n) for storing the distinct sums in a set.

Solution

We iterate over each cell (i, j) in the grid, and treat that cell as the center of a potential rhombus (area = 0 case). Then, for every possible rhombus size d (starting at 1), we first check if the rhombus is valid by ensuring that the bottom vertex and left/right boundaries remain within the grid. If valid, calculate the border sum along the four edges while ensuring that each border cell is added exactly once. This is done by:

  • Summing the top-left to top-right edge.
  • Summing the top-right to bottom-right edge.
  • Summing the bottom-right to bottom-left edge.
  • Summing the bottom-left to top-left edge (excluding the endpoints to avoid duplication).

Gather all distinct sums, sort them in descending order, and return the top three or fewer if less than three distinct sums are available.

Code Solutions

# Python solution with detailed comments

class Solution:
    def getBiggestThree(self, grid):
        m, n = len(grid), len(grid[0])
        distinct_sums = set()
        
        # Helper function to compute the border sum of a rhombus of size d starting at (i, j)
        def compute_rhombus_sum(i, j, d):
            total = 0
            # From top to right vertex (including both endpoints)
            for k in range(d + 1):
                total += grid[i + k][j + k]
            # From right vertex to bottom vertex (excluding the first point to avoid duplicate)
            for k in range(1, d + 1):
                total += grid[i + d + k][j + d - k]
            # From bottom vertex to left vertex (excluding the first point)
            for k in range(1, d + 1):
                total += grid[i + 2*d - k][j - k]
            # From left vertex back to top (excluding first and last points to avoid duplicates)
            for k in range(1, d):
                total += grid[i + d - k][j - d + k]
            return total
        
        # Iterate over each cell as potential rhombus top vertex
        for i in range(m):
            for j in range(n):
                # Area 0 rhombus (just a cell)
                distinct_sums.add(grid[i][j])
                # Try to form rhombus of larger sizes
                d = 1
                while i + 2 * d < m and j + d < n and j - d >= 0:
                    rhombus_sum = compute_rhombus_sum(i, j, d)
                    distinct_sums.add(rhombus_sum)
                    d += 1
        
        # Sort all distinct sums in descending order and return top three
        return sorted(distinct_sums, reverse=True)[:3]

# Example usage:
# sol = Solution()
# print(sol.getBiggestThree([[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]]))
← Back to All Questions