2428. Maximum Sum of an Hourglass

Problem Description

You are given a matrix of integers with dimensions m x n. The task is to find the maximum sum of an "hourglass" shape within this matrix. An hourglass in this context is defined as a subset of the matrix with the following form:

X X X
  X
X X X

Here, X represents the elements which are part of the hourglass. To get the sum of an hourglass, you add up all the Xs. The goal is to find the hourglass with the highest sum within the given matrix. Take note that the hourglass should be fully contained within the matrix and cannot be rotated.

Intuition

The intuition behind the solution is based on systematic exploration. Since the hourglass has a fixed shape, we can deduce that we need to scan through the matrix by moving the center of the hourglass from one feasible position to another. The 'feasible positions' are those where an hourglass can be fully contained in the matrix. This means that the center cannot be on the border; it has to be at least one row and one column away from the edges.

Once we have determined where the center of an hourglass can be, we can calculate the sum of the elements for each hourglass configuration. To avoid redundant calculations, we calculate the sum of the full block of 3x3 and then subtract the values that do not belong to the hourglass shape (the corners).

We keep track of the maximum sum we find while iterating over all possible positions for the center of the hourglass. This method ensures that we check every possible hourglass and find the one with the maximum sum, which is our final answer.

Learn more about Prefix Sum patterns.

Solution Approach

The algorithm for solving this problem is straightforward and doesn't require complex data structures or advanced patterns. Here's a step-by-step breakdown of the solution:

We first initialize a variable ans to store the maximum sum of any hourglass found during the traversal of the matrix.
The problem is then approached by considering each element of the matrix that could potentially be the center of an hourglass. We must ensure that these centers are not on the border of the matrix because an hourglass cannot fit there. Thus, we start iterating from the second row and column ((1,1) considering 0-based indexing) up to the second-to-last row and column ((m - 2, n - 2)).
For each possible center of the hourglass at position (i, j), we compute the sum of the hourglass by adding up all the elements in the 3x3 block centered at (i, j) by using a nested loop or a sum with a comprehension list.
After getting the sum of the entire 3x3 block, we need to subtract the elements that don't belong to the hourglass. These are the elements at positions (i, j - 1) and (i, j + 1). So we subtract the values at these positions from the sum of the 3x3 block to get the correct hourglass sum.
We then compare this sum with our current maximum value stored in ans and update ans if the current sum is greater.
After we have completed the traversal, the ans variable contains the highest sum of any hourglass in the matrix. This value is returned as the final answer.

The code provided makes use of list comprehensions for summing elements and simple for-loops for traversal. The Python max function is utilized to keep track of the maximum value, and the nested loops along with indexing allow for accessing matrix elements.

In essence, the algorithm is O(m*n), where m is the number of rows and n is the number of columns in the matrix, because we need to check each potential center for the hourglass. This is an example of a brute-force approach since it checks all possible hourglass configurations in the matrix. Despite the brute-force nature, it is efficient enough for the problem's constraints because the size of an hourglass is constant and small.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a simple example to illustrate the solution approach. Suppose we are given the following 3x4 matrix of integers:

1 1 1 0
0 1 0 0
1 1 1 0

According to our solution approach, we must find the maximum sum of an "hourglass" shape within this matrix. Here, the potential centers for the hourglass are marked with C in the matrix:

1 1 1 0
0 C 0 0
1 1 1 0

We can see that there is only one feasible center at position 1,1 (0-based indexing), since it is the only position that allows a full hourglass to be contained within the matrix. We will now compute the sum of the hourglass centered at this position.

Start at the center position (1,1).
Consider the 3x3 block centered at (1,1), which includes all the cells adjacent to it directly or diagonally. For this hourglass, the block is:
```
1 1 1
0 1 0
1 1 1
```
Now, to find the sum of the hourglass, we add up the elements within this 3x3 block, except for the corners that are not part of the hourglass:
```
1 + 1 + 1
  + 1 +
1 + 1 + 1
```
The sum of the hourglass is 1 + 1 + 1 + 1 + 1 + 1 + 1 = 7.
Since there is only one feasible hourglass in this example, the maximum sum is 7.
We can conclude that the maximum hourglass sum in the given matrix is 7.

This illustrates the solution approach where we systematically explore each potential center and calculate the corresponding hourglass sum to find the maximum. In this case, the answer is straightforward since there's only one possible hourglass. However, in a larger matrix, we would iterate over every element that could be the center of an hourglass while avoiding the border elements. After iterating through all potential centers, we would compare the sums and return the maximum one found.

Solution Implementation

1class Solution:
2    def maxSum(self, grid: List[List[int]]) -> int:
3        # Get the dimensions of the grid
4        num_rows, num_columns = len(grid), len(grid[0])
5      
6        # Initialize the maximum hourglass sum to 0
7        max_hourglass_sum = 0
8      
9        # Traverse the grid, avoiding the borders since hourglasses extend beyond a single point
10        for row in range(1, num_rows - 1):
11            for col in range(1, num_columns - 1):
12                # Calculate the sum of the current hourglass
13                hourglass_sum = (
14                    grid[row - 1][col - 1] +
15                    grid[row - 1][col] +
16                    grid[row - 1][col + 1] +
17                    grid[row][col] + # The center of the hourglass
18                    grid[row + 1][col - 1] +
19                    grid[row + 1][col] +
20                    grid[row + 1][col + 1]
21                )
22              
23                # Update the maximum hourglass sum if the current one is greater
24                max_hourglass_sum = max(max_hourglass_sum, hourglass_sum)
25              
26        # Return the maximum hourglass sum found
27        return max_hourglass_sum
28

1class Solution {
2    // Computes the maximum sum of any hourglass-shaped subset in a 2D grid.
3    public int maxSum(int[][] grid) {
4        // Dimensions of the grid
5        int rows = grid.length;
6        int columns = grid[0].length;
7      
8        // Variable to hold the maximum sum of hourglass found so far
9        int maxHourglassSum = 0;
10      
11        // Loop through each cell, but avoid the edges where hourglass cannot fit
12        for (int i = 1; i < rows - 1; ++i) {
13            for (int j = 1; j < columns - 1; ++j) {
14                // Compute the sum of the current hourglass
15                // Initialize the sum with the negative value of the center elements to the left and right
16                // Since we are going to add all nine cells, subtracting the unwanted cells in advance
17                // prevents them from being included in the final hourglass sum.
18                int hourglassSum = -grid[i][j - 1] - grid[i][j + 1];
19              
20                // Add the sum of the entire 3x3 block around the current cell
21                for (int x = i - 1; x <= i + 1; ++x) {
22                    for (int y = j - 1; y <= j + 1; ++y) {
23                        hourglassSum += grid[x][y];
24                    }
25                }
26
27                // Update the maximum sum if the current hourglass sum is greater than the maximum sum found so far
28                maxHourglassSum = Math.max(maxHourglassSum, hourglassSum);
29            }
30        }
31
32        // Return the maximum sum of an hourglass found in the grid
33        return maxHourglassSum;
34    }
35}
36```
37
38This code snippet is for a class named `Solution` containing a method `maxSum` that calculates the maximum sum of an "hourglass" in a 2-dimensional grid. An hourglass shape is defined by a pattern of cells from the grid in the following form:
39
40```
41a b c
42  d
43e f g
44

1#include <vector>
2#include <algorithm> // For std::max
3
4using namespace std;
5
6class Solution {
7public:
8    int maxSum(vector<vector<int>>& grid) {
9        // Get the number of rows 'm' and columns 'n' from the grid
10        int numRows = grid.size(), numCols = grid[0].size();
11      
12        // Initialize the variable to hold the maximum sum of an hourglass
13        int maxHourglassSum = 0;
14      
15        // Iterate over each potential center of an hourglass
16        for (int row = 1; row < numRows - 1; ++row) {
17            for (int col = 1; col < numCols - 1; ++col) {
18              
19                // Calculate the sum of the current hourglass, which includes:
20                // - The sum of the top row (3 cells)
21                // - The center cell
22                // - The sum of the bottom row (3 cells)
23                int hourglassSum = grid[row - 1][col - 1] + grid[row - 1][col] + grid[row - 1][col + 1]
24                                  + grid[row][col]
25                                  + grid[row + 1][col - 1] + grid[row + 1][col] + grid[row + 1][col + 1];
26              
27                // Update the maximum hourglass sum found so far
28                maxHourglassSum = max(maxHourglassSum, hourglassSum);
29            }
30        }
31      
32        // Return the maximum hourglass sum
33        return maxHourglassSum;
34    }
35};
36

1function maxSum(grid: number[][]): number {
2    // Get the row count (m) and column count (n) of the grid.
3    const rowCount = grid.length;
4    const colCount = grid[0].length;
5  
6    // Initialize the variable to store the maximum sum of the hourglass.
7    let maxHourglassSum = 0;
8
9    // Loop over the internal cells where an hourglass can be formed,
10    // excluding the borders because an hourglass shape cannot fit there.
11    for (let row = 1; row < rowCount - 1; ++row) {
12        for (let col = 1; col < colCount - 1; ++col) {
13            // Initialize the sum of the current hourglass.
14            // Starting with the center value negation, as it's added twice in the nested loop.
15            let hourglassSum = -grid[row][col];
16
17            // Sum values of the hourglass, three rows and three columns at a time.
18            for (let x = row - 1; x <= row + 1; ++x) {
19                for (let y = col - 1; y <= col + 1; ++y) {
20                    hourglassSum += grid[x][y];
21                }
22            }
23
24            // Update the maximum sum with the higher of the two values: the current max and the current hourglass sum.
25            maxHourglassSum = Math.max(maxHourglassSum, hourglassSum);
26        }
27    }
28
29    // Return the maximum hourglass sum found.
30    return maxHourglassSum;
31}
32```
33
34In this code, the function `maxSum` calculates the maximum sum of any hourglass-shaped sum in a 2D grid array where each hourglass shape is formed by a subset of values in a pattern that resembles an hourglass:
35
36```
37a b c
38  d
39e f g
40

Time and Space Complexity

Time Complexity

The time complexity of the given code is primarily determined by the two nested loops that iterate over the elements of the grid, excluding the outermost rows and columns. For each element grid[i][j] located inside these bounds (thus (m-2)*(n-2) elements), we are computing the sum of the 3x3 hourglass centered at grid[i][j]. This involves adding up 9 values for each valid i and j.

Therefore, we are performing a constant amount of work (specifically, 9 additions and 2 subtractions) for each hourglass shape. Given that there are (m-2)*(n-2) such hourglasses, the overall time complexity is O((m-2)*(n-2)*9), which simplifies to O(m*n) since the constant factor of 9 can be dropped in big O notation.

Space Complexity

The space complexity of the code is O(1), as it only uses a fixed number of variables and does not allocate any additional space that grows with the input size. The variable ans is used to keep track of the maximum sum, and temporary variables like s, i, j, x, and y are of a constant number as well. This code makes in-place calculations and does not require any extra space for data structures like arrays or lists that would depend on the input size.

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

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

Question 1 out of 10

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

Stack

Queue

Tree

Linked List

I don’t know