Maximum Sum of an Hourglass Solution In C++/Python/java/JS
Problem Description
You are given an m x n integer matrix grid. Return the maximum sum of the elements of an hourglass.
Note that an hourglass cannot be rotated and must be entirely contained within the matrix.
Example
Input: grid = [[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]]
Output: 30
Explanation: The cells shown above represent the hourglass with the maximum sum: 6 + 2 + 1 + 2 + 9 + 2 + 8 = 30.
Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: 35
Explanation: There is only one hourglass in the matrix, with the sum: 1 + 2 + 3 + 5 + 7 + 8 + 9 = 35.
Constraints
- m == grid.length
- n == grid[i].length
- 3 <= m, n <= 150
- 0 <= grid[i][j] <= 10^6
The goal here is to find the maximum sum of an hourglass in a given matrix. Since we need to compute the sum of all possible hourglasses in the matrix, the challenge is to traverse the matrix efficiently and keep track of the largest sum encountered. Let’s explore how we can approach this problem to find the maximum hourglass sum!
Optimal Approach
Intuition
When solving the hourglass sum problem in a 2D matrix, we first recognize the shape and structure of an hourglass. It is a 3-row pattern where the top and bottom rows contribute three elements each, and the middle row contributes just one element centered beneath the top middle value. To compute the largest sum of such hourglass patterns, we initialize a variable maxSum to store the highest hourglass sum encountered. Then, we calculate the number of rows and columns in the matrix to set the bounds of our iteration. We start our loops from index 1 (second row and column) and stop one before the last, ensuring we do not go out of bounds when accessing neighbors for the hourglass pattern.
As we loop through each valid center of an hourglass, we calculate the sum of its seven contributing elements and compare it with the current maxSum. If the newly calculated sum is greater, we update maxSum. This process is repeated for all possible hourglass centers in the matrix. By the end of the iteration, maxSum contains the largest hourglass sum found. This approach ensures we never miss any possible hourglass and provides a time-efficient O(n²) solution, where n is the number of rows (or columns) since each hourglass is processed in constant time.
Approach
Step 1: Initialize Variables
We begin by setting up the maxSum variable, initialized to 0, which will store the maximum sum of an hourglass in the matrix. Additionally, the dimensions of the matrix are calculated: rows is set to the number of rows in the matrix, and cols is set to the number of columns.
Step 2: Traverse the Matrix
We loop through the matrix, starting from the second row (i = 1) and the second column (j = 1), because an hourglass requires the center element and the surrounding ones. For each valid hourglass center, we calculate the sum of the hourglass elements, which includes the top, middle, and bottom rows of the hourglass. The sum of these elements is stored in currentSum.
Step 3: Update maxSum
For each calculated currentSum, we compare it with the current maxSum and update maxSum to the larger of the two values. This ensures that after processing all possible hourglasses, maxSum holds the largest sum encountered.
Step 4: Return the Result
After traversing the entire matrix and calculating all possible hourglass sums, the value stored in maxSum represents the maximum hourglass sum. This value is then returned as the final result.
Dry Run
Input:
grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Initialization:
maxSum = 0, to store the maximum hourglass sum.
Rows = 3, Columns = 3, representing the matrix dimensions.
Matrix Traversal:
We process the matrix to calculate the sum of the only possible hourglass.
Start with i = 1, j = 1 (the center of the hourglass).
currentSum is calculated by adding the elements forming the hourglass:
grid[i-1][j-1] + grid[i-1][j] + grid[i-1][j+1]
- grid[i][j]
- grid[i+1][j-1] + grid[i+1][j] + grid[i+1][j+1]
= 1 + 2 + 3 + 5 + 7 + 8 + 9 = 35
maxSum is updated: max(maxSum, currentSum) = max(0, 35) = 35.
Final Output:
The maximum sum of an hourglass is 35.
Return 35.
Code for All Languages
C++
class Solution {
public:
// Function to calculate the maximum hourglass sum in the grid
int maxSum(vector<vector<int>>& grid) {
// Get the number of rows and columns in the grid
int rows = grid.size(), cols = grid[0].size();
// Variable to keep track of the maximum hourglass sum
int max_sum = 0;
// Iterate over the grid starting from the second row and column,
// and stopping one row and column before the end to form hourglasses
for (int i = 1; i < rows - 1; ++i) {
for (int j = 1; j < cols - 1; ++j) {
// Calculate the sum of the current hourglass
int current_sum = grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] // Top row of the hourglass
+ grid[i][j] // Middle element of the hourglass
+ grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]; // Bottom row of the hourglass
// Update the maximum sum if the current hourglass sum is greater
max_sum = max(max_sum, current_sum);
}
}
// Return the maximum hourglass sum
return max_sum;
}
};Java
class Solution {
// Function to calculate the maximum hourglass sum in the grid
public int maxSum(int[][] grid) {
// Get the number of rows and columns in the grid
int rows = grid.length;
int cols = grid[0].length;
// Variable to keep track of the maximum hourglass sum
int maxSum = 0;
// Iterate over the grid starting from the second row and column,
// and stopping one row and column before the end to form hourglasses
for (int i = 1; i < rows - 1; i++) {
for (int j = 1; j < cols - 1; j++) {
// Calculate the sum of the current hourglass
int currentSum = grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] // Top row of the hourglass
+ grid[i][j] // Middle element of the hourglass
+ grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]; // Bottom row of the hourglass
// Update the maximum sum if the current hourglass sum is greater
maxSum = Math.max(maxSum, currentSum);
}
}
// Return the maximum hourglass sum
return maxSum;
}
}Python
class Solution:
def maxSum(self, grid: List[List[int]]) -> int:
# Get the number of rows and columns in the grid
rows = len(grid)
cols = len(grid[0])
# Variable to keep track of the maximum hourglass sum
max_sum = 0
# Iterate over the grid starting from the second row and column,
# and stopping one row and column before the end to form hourglasses
for i in range(1, rows - 1):
for j in range(1, cols - 1):
# Calculate the sum of the current hourglass
current_sum = grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] # Top row of the hourglass
current_sum += grid[i][j] # Middle element of the hourglass
current_sum += grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1] # Bottom row of the hourglass
# Update the maximum sum if the current hourglass sum is greater
max_sum = max(max_sum, current_sum)
# Return the maximum hourglass sum
return max_sum
Javascript
var maxSum = function(grid) {
// Get the number of rows and columns in the grid
const rows = grid.length;
const cols = grid[0].length;
// Variable to keep track of the maximum hourglass sum
let maxSum = 0;
// Iterate over the grid starting from the second row and column,
// and stopping one row and column before the end to form hourglasses
for (let i = 1; i < rows - 1; i++) {
for (let j = 1; j < cols - 1; j++) {
// Calculate the sum of the current hourglass
let currentSum = grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] // Top row of the hourglass
currentSum += grid[i][j] // Middle element of the hourglass
currentSum += grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]; // Bottom row of the hourglass
// Update the maximum sum if the current hourglass sum is greater
maxSum = Math.max(maxSum, currentSum);
}
}
// Return the maximum hourglass sum
return maxSum;
};
Time Complexity : O(n*m)
Matrix Traversal
For a matrix of size n x m, we traverse each row and column exactly once.
For each element in the matrix, we calculate the sum of the hourglass, which involves accessing 7 elements, performing addition, and comparing to update the maximum sum. Each of these operations takes constant time. Thus, traversing all possible hourglasses takes O((n - 2) * (m - 2)) time, where n and m are the number of rows and columns, respectively.
Overall Time Complexity
The total time complexity is O((n - 2) * (m - 2)), which simplifies to O(n * m) since we traverse most of the matrix.
Space Complexity : O(1)
Auxiliary Space Complexity: O(1)
The auxiliary space includes the constant number of variables such as currentSum and maxSum, which take O(1) space.
Since no additional data structures are used beyond the input matrix, the auxiliary space complexity is O(1).
Total Space Complexity: O(n * m)
The input matrix grid itself takes O(n * m) space, where n is the number of rows and m is the number of columns. No additional data structures are created, so the total space complexity is dominated by the matrix size.
Thus, the total space complexity is O(n * m).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
You are given an n×n integer matrix. You can repeatedly choose any two adjacent elements (sharing a border) and multiply both by −1.
Return the maximum possible sum of the matrix's elements after applying the operation optimally.
Given a m x n matrix mat and an integer k, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for:
1) i - k <= r <= i + k,
2) j - k <= c <= j + k, and
3) (r, c) is a valid position in the matrix.