Maximum Sum of an Hourglass

Maximum Sum of an Hourglass

1. What is this problem about?

The Maximum Sum of an Hourglass problem asks you to find the highest sum among all possible "hourglass" shapes within a 2D matrix. An hourglass in a matrix consists of seven elements arranged like this: three elements in a top row, one element in the middle (directly below the middle of the top row), and three elements in a bottom row (directly below the middle row). You need to scan the entire matrix, calculate the sum for every valid hourglass, and return the maximum value found.

2. Why is this asked in interviews?

This "Maximum Sum of an Hourglass interview question" is commonly used by companies like Zoho and Nutanix to test a candidate's basic matrix manipulation skills. It evaluates whether you can correctly handle 2D indices and boundary conditions. While the problem itself isn't conceptually difficult, it requires attention to detail—specifically, ensuring that you don't go out of bounds while accessing the rows and columns required for each hourglass shape.

3. Algorithmic pattern used

The "Array, Matrix, Prefix Sum interview pattern" involves iterating through the matrix with nested loops. For a matrix of size R x C, you can only start an hourglass at indices (i, j) where i + 2 < R and j + 2 < C. This ensures the 3x3 area required for the hourglass is available. While a prefix sum could be used to optimize row sums, for a fixed shape like an hourglass, a direct summation of the seven specific indices is usually the most straightforward and efficient approach (O(R*C)).

4. Example explanation

Matrix: 1 1 1 0 0 1 0 0 1 1 1 0 0 0 0 0

• First Hourglass at (0,0): Top [1,1,1], Mid [1], Bottom [1,1,1]. Sum = 7.
• Moving one column right (0,1): Top [1,1,0], Mid [0], Bottom [1,1,0]. Sum = 3.
• Moving one row down (1,0): Top [0,1,0], Mid [1], Bottom [0,0,0]. Sum = 2. The maximum hourglass sum in this small matrix is 7.

5. Common mistakes candidates make

In the "Maximum Sum of an Hourglass coding problem," the most frequent mistake is incorrect indexing. Candidates often try to start an hourglass too close to the right or bottom edge, leading to "Index Out of Bounds" errors. Another mistake is forgetting the middle element of the hourglass or including extra elements from the middle row. Some also initialize the max_sum to 0, which might be incorrect if the matrix can contain negative numbers (though hourglass problems usually involve non-negative integers).

6. Interview preparation tip

Practice visualizing the matrix as a coordinate system where (row, col) represents (y, x). When dealing with fixed-shape problems, always write out the relative offsets first. For an hourglass at (r, c), the indices are (r, c), (r, c+1), (r, c+2), (r+1, c+1), (r+2, c), (r+2, c+1), (r+2, c+2). Having this list ready before you start coding will prevent most logic errors and show the interviewer you have a structured approach to matrix problems.