1878. Get Biggest Three Rhombus Sums in a Grid LeetCode Solution
In this guide, you will get 1878. Get Biggest Three Rhombus Sums in a Grid LeetCode Solution with the best time and space complexity. The solution to Get Biggest Three Rhombus Sums in a Grid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Get Biggest Three Rhombus Sums in a Grid solution in C++
- Get Biggest Three Rhombus Sums in a Grid solution in Java
- Get Biggest Three Rhombus Sums in a Grid solution in Python
- Additional Resources
Problem Statement of Get Biggest Three Rhombus Sums in a Grid
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. Below is an image of four valid rhombus shapes with the corresponding colored cells that should be included in each rhombus sum:
Note that the rhombus can have an area of 0, which is depicted by the purple rhombus in the bottom right corner.
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.
Example 1:
Input: grid = [[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]]
Output: [228,216,211]
Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above.
– Blue: 20 + 3 + 200 + 5 = 228
– Red: 200 + 2 + 10 + 4 = 216
– Green: 5 + 200 + 4 + 2 = 211
Example 2:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: [20,9,8]
Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above.
– Blue: 4 + 2 + 6 + 8 = 20
– Red: 9 (area 0 rhombus in the bottom right corner)
– Green: 8 (area 0 rhombus in the bottom middle)
Example 3:
Input: grid = [[7,7,7]]
Output: [7]
Explanation: All three possible rhombus sums are the same, so return [7].
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 105
Complexity Analysis
- Time Complexity: O(n^4)
- Space Complexity: O(1)
1878. Get Biggest Three Rhombus Sums in a Grid LeetCode Solution in C++
class Solution {
public:
vector<int> getBiggestThree(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
set<int> sums;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
for (int sz = 0; i + sz < m && i - sz >= 0 && j + 2 * sz < n; ++sz) {
const int sum = sz == 0 ? grid[i][j] : getSum(grid, i, j, sz);
sums.insert(sum);
if (sums.size() > 3)
sums.erase(sums.begin());
}
return vector<int>(sums.rbegin(), sums.rend());
}
private:
// Returns the sum of the rhombus, where the top grid is (i, j) and the edge
// size is `sz`.
int getSum(const vector<vector<int>>& grid, int i, int j, int sz) {
int x = i;
int y = j;
int sum = 0;
// Go left down.
for (int k = 0; k < sz; ++k)
sum += grid[--x][++y];
// Go right down.
for (int k = 0; k < sz; ++k)
sum += grid[++x][++y];
// Go right up.
for (int k = 0; k < sz; ++k)
sum += grid[++x][--y];
// Go left up.
for (int k = 0; k < sz; ++k)
sum += grid[--x][--y];
return sum;
}
};
/* code provided by PROGIEZ */1878. Get Biggest Three Rhombus Sums in a Grid LeetCode Solution in Java
class Solution {
public int[] getBiggestThree(int[][] grid) {
final int m = grid.length;
final int n = grid[0].length;
TreeSet<Integer> sums = new TreeSet<>();
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
for (int sz = 0; i + sz < m && i - sz >= 0 && j + 2 * sz < n; ++sz) {
final int sum = sz == 0 ? grid[i][j] : getSum(grid, i, j, sz);
sums.add(sum);
if (sums.size() > 3)
sums.pollFirst();
}
return sums.descendingSet().stream().mapToInt(Integer::intValue).toArray();
}
// Returns the sum of the rhombus, where the top grid is (i, j) and the edge
// size is `sz`.
private int getSum(int[][] grid, int i, int j, int sz) {
int x = i;
int y = j;
int sum = 0;
// Go left down.
for (int k = 0; k < sz; ++k)
sum += grid[--x][++y];
// Go right down.
for (int k = 0; k < sz; ++k)
sum += grid[++x][++y];
// Go right up.
for (int k = 0; k < sz; ++k)
sum += grid[++x][--y];
// Go left up.
for (int k = 0; k < sz; ++k)
sum += grid[--x][--y];
return sum;
}
}
// code provided by PROGIEZ1878. Get Biggest Three Rhombus Sums in a Grid LeetCode Solution in Python
from sortedcontainers import SortedSet
class Solution:
def getBiggestThree(self, grid: list[list[int]]) -> list[int]:
m = len(grid)
n = len(grid[0])
sums = SortedSet()
for i in range(m):
for j in range(n):
sz = 0
while i + sz < m and i - sz >= 0 and j + 2 * sz < n:
summ = grid[i][j] if sz == 0 else self._getSum(grid, i, j, sz)
sums.add(summ)
if len(sums) > 3:
sums.pop(0)
sz += 1
return sums
def _getSum(self, grid: list[list[int]], i: int, j: int, sz: int) -> int:
"""
Returns the sum of the rhombus, where the top grid is (i, j) and the edge
size is `sz`.
"""
x = i
y = j
summ = 0
# Go left down.
for _ in range(sz):
x -= 1
y += 1
summ += grid[x][y]
# Go right down.
for _ in range(sz):
x += 1
y += 1
summ += grid[x][y]
# Go right up.
for _ in range(sz):
x += 1
y -= 1
summ += grid[x][y]
# Go left up.
for _ in range(sz):
x -= 1
y -= 1
summ += grid[x][y]
return summ
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.