Maximum Sum Of An Hourglass - Leetcode Solution

The Maximum Sum of an Hourglass problem is a relatively simple problem that can be solved using a brute force approach. The problem can be stated as follows:

Given a 2D array of integers of size nxm, find the hourglass with the maximum sum of its elements.

An hourglass in the array is defined as a subset of the array consisting of 7 elements, which are arranged in the shape of an hourglass. The elements of the hourglass may be non-adjacent in the original array.

For example, given the following 2D array:

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

The hourglasses are as follows:

1 1 1 
  1 
1 1 1 

1 0 0 
  1 
1 0 0 

1 1 1 
  0 
1 1 1 

0 0 0 
  0 
0 0 0 

0 0 0 
  0 
0 0 0 

The hourglass with the maximum sum of its elements is the first one, with a sum of 7.

Solution:

One approach to solving the Maximum Sum of an Hourglass problem is to use a brute force approach. We can start by iterating through each element in the array, and for each element, construct the hourglass that includes that element.

To construct the hourglass, we need to find the 6 elements that surround the central element, and add them together. The hourglass sum is then the sum of all 7 elements.

To find the maximum sum of all the hourglasses, we can simply keep track of the maximum sum seen so far, and update it whenever a new maximum is found.

Here is Python code for the solution:

def max_hourglass_sum(arr): max_sum = None for i in range(len(arr)-2): for j in range(len(arr[0])-2): hourglass_sum = arr[i][j] + arr[i][j+1] + arr[i][j+2] +
arr[i+1][j+1] +
arr[i+2][j] + arr[i+2][j+1] + arr[i+2][j+2] if max_sum is None or hourglass_sum > max_sum: max_sum = hourglass_sum return max_sum

The time complexity of this solution is O(n^2), where n is the size of the array. This is because we need to iterate through every element in the array, and for each element, we need to access 6 other elements to construct the hourglass. The space complexity is O(1), since we only need to store the maximum sum seen so far.

1