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:

1X X X
2  X
3X 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:

1. We first initialize a variable ans to store the maximum sum of any hourglass found during the traversal of the matrix.

2. 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)).

3. 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.

4. 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.

5. We then compare this sum with our current maximum value stored in ans and update ans if the current sum is greater.

6. 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.

Example Walkthrough

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

11 1 1 0
20 1 0 0
31 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:

11 1 1 0
20 C 0 0
31 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.

1. Start at the center position (1,1).

2. 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:

   11 1 1
   20 1 0
   31 1 1

3. 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:

   11 + 1 + 1
   2  + 1 +
   31 + 1 + 1

   The sum of the hourglass is 1 + 1 + 1 + 1 + 1 + 1 + 1 = 7.

4. Since there is only one feasible hourglass in this example, the maximum sum is 7.

5. 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

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.