1878. Get Biggest Three Rhombus Sums in a Grid


Problem Description

In this problem, we're given a 2D matrix of integers and we need to calculate what are referred to as "rhombus sums". A rhombus sum is defined as the sum of the elements that form the border of a regular rhombus within the grid. The rhombus must be oriented like a square rotated by 45 degrees and its vertices need to align with cells in the grid. Interesting to note is that a rhombus can have an area of zero, which effectively means it is just a single point in the grid. Our goal is to find the three largest distinct rhombus sums and return them in descending order. If there aren't three distinct values, we simply return all the distinct sums we found.

Intuition

To efficiently solve this problem, we need a way to quickly compute the sum of the borders of potential rhombuses. We use a technique called prefix sums to help with this - a method that involves creating an array that stores the cumulative sum of elements of an input array up to each index. This allows us to calculate the sum of any subarray in constant time once the prefix sum array has been set up.

To apply prefix sums to this 2D case, we need two prefix sum arrays (s1 and s2) to handle the two diagonals of the rhombus. s1 array stores sums of elements along the upper-left to lower-right diagonals, while s2 stores sums of elements along the upper-right to lower-left diagonals. This allows us to calculate the sum of each diagonal segment of our potential rhombuses quickly.

Once we have our prefix sum arrays, we iterate over all possible centers of rhombuses in our grid. We start by adding the center cell value (a rhombus of zero area) to an ordered set ss. This ordered set automatically sorts any new entries and helps us maintain only the top three sums which are required for the output.

We then enumerate the potential side lengths of rhombuses, calculating the sum of the rhombus border using our prefix sums, which can be computed with some careful indexing into our s1 and s2 arrays. We subtract areas that are counted twice because we are interested in the border sum only. We add each sum to the ordered set ss, ensuring we keep the set size to a maximum of three by removing the smallest whenever necessary.

Finally, we return the elements of our ordered set in reverse order since they're maintained in ascending order, and we need them in descending order according to the problem requirements.

Learn more about Math, Prefix Sum, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The solution involves calculating rhombus sums within a grid by utilizing several programming patterns and algorithms:

  1. Prefix Sums: To allow constant-time lookup of the sum of elements along a diagonal, we construct two prefix sum matrices, s1 and s2. These prefix sum matrices represent cumulative sums along two different diagonal directions — s1 for the upper-left to lower-right diagonal and s2 for the upper-right to lower-left diagonal. The sum of elements in a diagonal slice of the matrix can then be retrieved by a simple subtraction operation between two elements in a prefix sum matrix.

    Here's how prefix sums are pre-calculated:

    1for every cell (i, j):
    2    s1[i][j] = s1[i - 1][j - 1] + grid[i - 1][j - 1]
    3    s2[i][j] = s2[i - 1][j + 1] + grid[i - 1][j - 1]
  2. Enumeration of Possible Centers: Since the rhombus is defined by its center and size, we iterate over every possible center in the matrix:

    1for i: 1 to m,
    2for j: 1 to n

    Where m and n are the dimensions of the matrix.

  3. Ordered Sets: An ordered set ss is an essential data structure used. Whenever a sum is computed, it's added to this set, which takes care of insertion in sorted order. To maintain the top three sums, we ensure the size of this set doesn't exceed three, removing the smallest element if necessary.

  4. Calculation of Rhombus Borders: For each center and for each possible rhombus size, we then calculate the sum of its borders using the following formula, with k being half the side length (from center to border):

    1a = s1[i + k][j] - s1[i][j - k]
    2b = s1[i][j + k] - s1[i - k][j]
    3c = s2[i][j - k] - s2[i - k][j]
    4d = s2[i + k][j] - s2[i][j + k]
    5rhombus_sum = a + b + c + d - grid[i + k - 1][j - 1] + grid[i - k - 1][j - 1]

    This formula computes the sum of four sides of the rhombus while subtracting the overlapping corner cells to avoid double-counting.

  5. Edge Case Handling: We add the value of a single cell as a rhombus with zero area before evaluating larger rhombuses, ensuring single values are considered in the final set.

Lastly, because an ordered set maintains ascending order and the problem asks for descending order, the list of unique sums is reversed before returning.

The combination of these approaches results in an efficient and effective solution that leverages data pre-processing (prefix sums), ordered data management with automatic sorting (ordered set), and systematic iteration over potential solutions (enumeration of centers and sizes).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using a 3x3 grid of integers:

13 9 4
28 7 1
36 5 2

Step 1: Calculate s1 and s2 (prefix sum arrays). Here is s1:

10 0 0 0
20 3 0 0
30 8 19 0
40 6 20 13

And s2:

10 0 0 0
20 4 0 0
30 9 13 0
40 6 21 15

Explanation: In s1, s1[2][2] (which is 19) represents the sum of the upper-left to lower-right diagonal from the top-left corner up to the cell (1, 1) in the original grid, which includes 3, 7, and 9. Similarly, in s2, s2[2][2] (which is 13) represents the sum of the upper-right to lower-left diagonal up to the cell (1, 1), which includes 4, 7, and 2.

Step 2: We consider each cell as the center of a potential rhombus, starting with (1,1) as the center and a rhombus with zero area:

1(1,1): 8

We add 8 to our ordered set ss, which is now {8}.

Step 3: As this is a 3x3 grid, the maximum half-length k for a rhombus is 1. So, we only look for rhombuses of edge length 2 (half-length 1).

For cell (1,1):

1a = s1[2][1] - s1[1][0] = 8 - 0 = 8
2b = s1[1][2] - s1[0][1] = 19 - 0 = 19
3c = s2[1][0] - s2[0][1] = 0 - 0 = 0
4d = s2[2][1] - s2[1][2] = 9 - 19 = -10
5rhombus_sum = 8 + 19 + 0 - 10 - 7 = 10

We add 10 to our ordered set ss, which is now {8, 10}.

For cell (1,2):

1a = s1[2][2] - s1[1][1] = 19 - 3 = 16
2b = s1[1][3] - s1[0][2] = 0 - 0 = 0
3c = s2[1][1] - s2[0][2] = 13 - 0 = 13
4d = s2[2][2] - s2[1][3] = 13 - 0 = 13
5rhombus_sum = 16 + 0 + 13 + 13 - 7 = 35

We add 35 to set ss, which now becomes {8, 10, 35}.

Since we now have three distinct values and the set can't exceed three elements, we would typically check and remove the smallest if necessary. However, no removal is required here.

Repeating this process for other cells in the grid, we might get other sums, but since the set is already at capacity, only larger sums would replace the smaller ones.

Step 4: We've considered all possible centers. The ordered set ss contains the sums in ascending order:

1{8, 10, 35}

Step 5: We return the elements of ss in reverse order:

1[35, 10, 8]

Thus, the three largest distinct rhombus sums in descending order are 35, 10, and 8.

Solution Implementation

1from sortedcontainers import SortedSet
2from typing import List
3
4class Solution:
5    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
6        # Number of rows and columns in the grid
7        rows, cols = len(grid), len(grid[0])
8      
9        # Prefix sum arrays for diagonals going from top-left to bottom-right (s1)
10        # and top-right to bottom-left (s2)
11        diag_sum_tl_br = [[0] * (cols + 2) for _ in range(rows + 1)]
12        diag_sum_tr_bl = [[0] * (cols + 2) for _ in range(rows + 1)]
13      
14        # Pre-calculate the diagonal prefix sums
15        for i, row in enumerate(grid, 1):
16            for j, value in enumerate(row, 1):
17                diag_sum_tl_br[i][j] = diag_sum_tl_br[i - 1][j - 1] + value
18                diag_sum_tr_bl[i][j] = diag_sum_tr_bl[i - 1][j + 1] + value
19              
20        # Sorted set to store the unique sums and keep them sorted
21        unique_sums = SortedSet()
22      
23        # Calculate rhombus sums and store them in the sorted set
24        for i, row in enumerate(grid, 1):
25            for j, value in enumerate(row, 1):
26                # Find the largest possible rhombus for the current cell
27                max_rhombus_size = min(i - 1, rows - i, j - 1, cols - j)
28              
29                # Add the single cell value (smallest rhombus)
30                unique_sums.add(value)
31              
32                # Iterate through all possible rhombus sizes
33                for size in range(1, max_rhombus_size + 1):
34                    a = diag_sum_tl_br[i + size][j] - diag_sum_tl_br[i][j - size]
35                    b = diag_sum_tl_br[i][j + size] - diag_sum_tl_br[i - size][j]
36                    c = diag_sum_tr_bl[i][j - size] - diag_sum_tr_bl[i - size][j]
37                    d = diag_sum_tr_bl[i + size][j] - diag_sum_tr_bl[i][j + size]
38                  
39                    # Sum the values of the rhombus edges and adjust for duplicate corners
40                    rhombus_sum = a + b + c + d - grid[i + size - 1][j - 1] + grid[i - size - 1][j - 1]
41                    unique_sums.add(rhombus_sum)
42                  
43                # Remove the smallest values to keep only the three largest unique sums
44                while len(unique_sums) > 3:
45                    unique_sums.remove(unique_sums[0])
46      
47        # The unique sums are sorted in ascending order, so we reverse them to get descending order
48        return list(unique_sums)[::-1]
49
1import java.util.TreeSet;
2
3class Solution {
4  
5    public int[] getBiggestThree(int[][] grid) {
6        int rows = grid.length, cols = grid[0].length;
7        // Precompute the prefix sums for the two diagonals
8        int[][] prefixSumDiag1 = new int[rows + 1][cols + 2];
9        int[][] prefixSumDiag2 = new int[rows + 1][cols + 2];
10      
11        // Calculating prefix sum for both diagonals
12        for (int i = 1; i <= rows; ++i) {
13            for (int j = 1; j <= cols; ++j) {
14                prefixSumDiag1[i][j] = prefixSumDiag1[i - 1][j - 1] + grid[i - 1][j - 1];
15                prefixSumDiag2[i][j] = prefixSumDiag2[i - 1][j + 1] + grid[i - 1][j - 1];
16            }
17        }
18      
19        // TreeSet will store the unique sums in sorted order
20        TreeSet<Integer> uniqueSums = new TreeSet<>();
21        for (int i = 1; i <= rows; ++i) {
22            for (int j = 1; j <= cols; ++j) {
23                // Calculate the limit for the size of the rhombus based on the current cell
24                int limit = Math.min(Math.min(i - 1, rows - i), Math.min(j - 1, cols - j));
25              
26                // Add the single cell value
27                uniqueSums.add(grid[i - 1][j - 1]);
28              
29                // Generate rhombus sums of increasing sizes
30                for (int k = 1; k <= limit; ++k) {
31                    int a = prefixSumDiag1[i + k][j] - prefixSumDiag1[i][j - k];
32                    int b = prefixSumDiag1[i][j + k] - prefixSumDiag1[i - k][j];
33                    int c = prefixSumDiag2[i][j - k] - prefixSumDiag2[i - k][j];
34                    int d = prefixSumDiag2[i + k][j] - prefixSumDiag2[i][j + k];
35                  
36                    // Add the rhombus sum, adjusting for the overlap
37                    uniqueSums.add(a + b + c + d - grid[i + k - 1][j - 1] - grid[i - k - 1][j - 1]);
38                }
39              
40                // Keep only the top 3 largest sums
41                while (uniqueSums.size() > 3) {
42                    uniqueSums.pollFirst();
43                }
44            }
45        }
46      
47        // Convert the TreeSet to an array
48        int[] largestSums = new int[uniqueSums.size()];
49        for (int i = 0; i < largestSums.length; ++i) {
50            largestSums[i] = uniqueSums.pollLast();
51        }
52      
53        return largestSums;
54    }
55}
56
1class Solution {
2public:
3    vector<int> getBiggestThree(vector<vector<int>>& grid) {
4        int rows = grid.size(), cols = grid[0].size();
5      
6        // Prefix sums for diagonals from top-left to bottom-right (s1)
7        // and for diagonals from top-right to bottom-left (s2)
8        vector<vector<int>> prefixSum1(rows + 1, vector<int>(cols + 2));
9        vector<vector<int>> prefixSum2(rows + 1, vector<int>(cols + 2));
10      
11        // Calculate the prefix sums for both diagonal directions.
12        for (int i = 1; i <= rows; ++i) {
13            for (int j = 1; j <= cols; ++j) {
14                prefixSum1[i][j] = prefixSum1[i - 1][j - 1] + grid[i - 1][j - 1];
15                prefixSum2[i][j] = prefixSum2[i - 1][j + 1] + grid[i - 1][j - 1];
16            }
17        }
18      
19        // Using a set to keep track of the unique rhombus sums and ensure they are sorted.
20        set<int> rhombusSums;
21      
22        // Iterate through each cell of the grid.
23        for (int i = 1; i <= rows; ++i) {
24            for (int j = 1; j <= cols; ++j) {
25                // Find the maximum possible rhombus side length from the current position.
26                int lenLimit = min({i - 1, rows - i, j - 1, cols - j});
27              
28                // Insert the single cell value as a rhombus of side length 0.
29                rhombusSums.insert(grid[i - 1][j - 1]);
30              
31                // Check all possible rhombuses starting from the current cell.
32                for (int k = 1; k <= lenLimit; ++k) {
33                    int sumA = prefixSum1[i + k][j] - prefixSum1[i][j - k];
34                    int sumB = prefixSum1[i][j + k] - prefixSum1[i - k][j];
35                    int sumC = prefixSum2[i][j - k] - prefixSum2[i - k][j];
36                    int sumD = prefixSum2[i + k][j] - prefixSum2[i][j + k];
37                  
38                    // Calculate the sum of the rhombus edges, subtract overlapping corners.
39                    rhombusSums.insert(sumA + sumB + sumC + sumD - grid[i + k - 1][j - 1] - grid[i - k - 1][j - 1]);
40                }
41              
42                // Make sure to only keep the largest three sums if there are more.
43                while (rhombusSums.size() > 3) {
44                    rhombusSums.erase(rhombusSums.begin());
45                }
46            }
47        }
48      
49        // Convert the set into a vector and reverse, as sets are in ascending order by default.
50        return vector<int>(rhombusSums.rbegin(), rhombusSums.rend());
51    }
52};
53
1//
2// The TreeSet object is a representation of a set of values, backed by a Red-Black Tree.
3// It supports efficient lookup, addition, and deletion operations, and maintains elements in sorted order.
4//
5
6// Utility functions for Red-Black Tree
7// ...
8
9let compareFn: Compare<number>;
10
11let treeRoot: RBTreeNode<number> | null = null;
12let treeSize: number = 0;
13
14// Initialization of the TreeSet
15function initializeTreeSet(collection: number[] = [], compare: Compare<number> = defaultCompare): void {
16    // Default comparison function if the user does not specify otherwise
17    function defaultCompare(l: number, r: number): number {
18        return l < r ? -1 : l > r ? 1 : 0;
19    }
20
21    compareFn = compare;
22    treeSize = 0;
23    // Construct the tree from the given collection
24    collection.forEach((val) => add(val));
25}
26
27// Returns the total number of elements in the TreeSet
28function size(): number {
29    return treeSize;
30}
31
32// Checks if a value exists in the TreeSet
33function has(val: number): boolean {
34    return !!find(val, treeRoot);
35}
36
37// Adds a value to the TreeSet if it doesn't already exist
38function add(val: number): boolean {
39    const successful: boolean = insert(val, treeRoot, null, false);
40    treeSize += successful ? 1 : 0;
41    return successful;
42}
43
44// Deletes a value from the TreeSet
45function deleteValue(val: number): boolean {
46    const deleted = deleteNode(val, treeRoot);
47    treeSize -= deleted ? 1 : 0;
48    return deleted;
49}
50
51// Finds the least element that is greater than or equal to the given value
52function ceil(val: number): number | undefined {
53    return findCeil(val, treeRoot);
54}
55
56// Finds the greatest element that is less than or equal to the given value
57function floor(val: number): number | undefined {
58    return findFloor(val, treeRoot);
59}
60
61// Finds the smallest element in the TreeSet
62function first(): number | undefined {
63    return firstNode(treeRoot)?.data;
64}
65
66// Finds the largest element in the TreeSet
67function last(): number | undefined {
68    return lastNode(treeRoot)?.data;
69}
70
71// Removes and returns the smallest element from the TreeSet
72function shift(): number | undefined {
73    const firstElement = first();
74    if (firstElement !== undefined) {
75        deleteValue(firstElement);
76    }
77    return firstElement;
78}
79
80// Removes and returns the largest element from the TreeSet
81function pop(): number | undefined {
82    const lastElement = last();
83    if (lastElement !== undefined) {
84        deleteValue(lastElement);
85    }
86    return lastElement;
87}
88
89// Iterator to traverse through all values in the TreeSet in ascending order
90function* values(): Generator<number, undefined, unknown> {
91    for (const val of inOrder(treeRoot)) {
92        yield val;
93    }
94    return undefined;
95}
96
97// ... additional functions and iterators continue here ...
98
99// Implementation details (e.g., tree rotations, insertion, deletion, etc.) for the Red-Black Tree
100// ...
101

Time and Space Complexity

The time complexity of the code is O(m * n * min(m, n)). This is because for each cell in the grid, the algorithm is iterating over a maximum of min(i - 1, m - i, j - 1, n - j) rhombuses, which is bounded by min(m, n), where m and n are the number of rows and columns of the matrix, respectively. The inner loop runs in O(k) time for each k due to the sum calculations for the rhombus sides without including corners, making the total time complexity O(m * n * min(m, n)).

The space complexity of the code is O(m * n) because of the space used by the s1 and s2 arrays, which store the prefix sums for the diagonals of the grid. Each array s1 and s2 has dimensions (m+1) x (n+2), but the extra space doesn't change the overall O(m * n) space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄