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.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Solution Approach
The solution involves calculating rhombus sums within a grid by utilizing several programming patterns and algorithms:
-
Prefix Sums: To allow constant-time lookup of the sum of elements along a diagonal, we construct two prefix sum matrices,
s1ands2. These prefix sum matrices represent cumulative sums along two different diagonal directions โs1for the upper-left to lower-right diagonal ands2for 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] -
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 nWhere
mandnare the dimensions of the matrix. -
Ordered Sets: An ordered set
ssis 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. -
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
kbeing 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.
-
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).
How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).
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]
491import 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}
561class 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};
531//
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// ...
101Which data structure is used to implement priority queue?
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.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
121import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
181function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Got a question?ย Ask the Teaching 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.