Maximum Sum of an Hourglass

📋

Problem

Imagine analyzing satellite images where you want to find the region shaped like an hourglass with the highest total intensity to detect hotspots.

Given a 2D integer matrix of size n x m, find the maximum sum of values forming an hourglass shape. An hourglass is defined as a subset of values with indices forming this pattern: a b c d e f g Return the maximum hourglass sum found in the matrix.

3 ≤ n, m ≤ 1000-10^6 ≤ matrix[i][j] ≤ 10^6

Edge cases: Matrix with all negative numbers → maximum sum is the least negative hourglassMatrix with minimum size 3x3 → only one hourglass possibleMatrix with large positive and negative values → test integer overflow handling

</>

IDE

def max_hourglass_sum(matrix: list[list[int]]) -> int:public int maxHourglassSum(int[][] matrix)int maxHourglassSum(vector<vector<int>>& matrix)function maxHourglassSum(matrix)

def max_hourglass_sum(matrix):
    # Write your solution here
    pass

class Solution {
    public int maxHourglassSum(int[][] matrix) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maxHourglassSum(vector<vector<int>>& matrix) {
    // Write your solution here
    return 0;
}

function maxHourglassSum(matrix) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Initializing max sum to 0 instead of -inf causes incorrect max when all sums are negative.✅ Initialize max_sum = float('-inf') (Python) or Integer.MIN_VALUE (Java) before loops.

Wrong: Sum of entire 3x3 block instead of hourglassSumming all 9 elements in 3x3 block instead of 7 hourglass elements.✅ Sum only elements at positions (i,j),(i,j+1),(i,j+2),(i+1,j+1),(i+2,j),(i+2,j+1),(i+2,j+2).

Wrong: Missing max hourglass at last valid positionLoop bounds off-by-one causing last hourglass to be skipped.✅ Loop i from 0 to n-3 inclusive and j from 0 to m-3 inclusive.

Wrong: Partial scan or first max hourglass returnedGreedy approach returning first max without scanning all hourglasses.✅ Scan all hourglass positions and update max sum accordingly.

Wrong: TLE or timeoutAlgorithm complexity worse than O(n*m), e.g., nested loops beyond fixed pattern or exponential.✅ Use direct nested loops scanning all hourglass positions once; avoid exponential or unnecessary nested loops.

✓

Test Cases

Try edge cases with smallest and negative-only matrices to solidify base cases.

Focus on loop bounds and pattern indexing to catch subtle off-by-one or greedy errors.

Ensure your solution is O(n*m) and does not use exponential or nested loops beyond fixed pattern.

t1_01basic

Input{"matrix":[[1,2,3,0,0],[0,0,0,0,0],[2,1,4,0,0],[0,0,0,0,0],[1,1,0,1,0]]}

Expected13

⏱ Performance - must finish in 2000ms

The hourglass with maximum sum is the one starting at (0,0): 1+2+3+0+2+1+4=13.

💡 Consider every possible hourglass starting point in the matrix.

💡 Sum the fixed pattern of 7 elements for each hourglass and track the maximum.

💡 Use nested loops from 0 to n-3 and 0 to m-3 and compute sums exactly as per pattern.

Why it failed: Incorrect max sum indicates missing or wrong hourglass sum calculation. Fix by correctly summing all 7 hourglass elements for each valid position.

✓ Correctly computes max hourglass sum for canonical example.

t1_02basic

Input{"matrix":[[1,1,1,0,0],[0,1,0,0,0],[1,1,1,0,0],[0,0,2,4,4],[0,0,0,2,0]]}

Expected10

⏱ Performance - must finish in 2000ms

Max hourglass sum is 10 from hourglass starting at (2,1): 1+1+0+2+0+2+4=10.

💡 Check all hourglasses including those overlapping bottom rows.

💡 Remember the hourglass center is the middle element of the second row.

💡 Sum elements at positions (i,j) to (i,j+2), (i+1,j+1), and (i+2,j) to (i+2,j+2).

Why it failed: Wrong output means hourglass sums are not computed for all valid positions or pattern indices are off. Fix indexing to match hourglass shape exactly.

✓ Correctly finds max hourglass sum for varied input.

t2_01edge

Input{"matrix":[[-1,-1,-1],[-1,-1,-1],[-1,-1,-1]]}

Expected-7

⏱ Performance - must finish in 2000ms

Only one hourglass possible; sum all elements: 7 * -1 = -7.

💡 Test minimum size matrix with all negative values.

💡 Ensure your code handles negative sums correctly and does not default to zero.

💡 Initialize max sum to -inf and update properly even if all sums are negative.

Why it failed: Failing this means code assumes non-negative sums or initializes max sum incorrectly. Fix by initializing max_sum to float('-inf') or equivalent.

✓ Correctly handles all negative values and minimum size matrix.

t2_02edge

Input{"matrix":[[1000000,-1000000,1000000],[-1000000,1000000,-1000000],[1000000,-1000000,1000000]]}

Expected3000000

⏱ Performance - must finish in 2000ms

Sum of hourglass is 1000000+(-1000000)+1000000+1000000+1000000+(-1000000)+1000000=3000000.

💡 Test large positive and negative values to check integer overflow handling.

💡 Use data types that can hold sums beyond single element range.

💡 Sum carefully and avoid integer overflow by using 64-bit integers or Python int.

Why it failed: Failing means integer overflow or incorrect sum calculation. Fix by using appropriate data types and summing carefully.

✓ Handles large positive and negative values without overflow.

t2_03edge

Input{"matrix":[[1,1,1],[1,1,1],[1,1,1]]}

Expected7

⏱ Performance - must finish in 2000ms

Only one hourglass possible; sum all 7 elements = 7.

💡 Test exact boundary size 3x3 matrix with all identical elements.

💡 Ensure code does not fail on smallest valid input size.

💡 Confirm hourglass sum calculation matches pattern exactly.

Why it failed: Failing means code does not handle smallest matrix size or sums wrong elements. Fix loop bounds and indexing.

✓ Correctly computes hourglass sum for smallest matrix.

t3_01corner

Input{"matrix":[[1,2,3,4],[0,0,0,0],[4,3,2,1],[0,0,0,0]]}

Expected15

⏱ Performance - must finish in 2000ms

Max hourglass sum is 15 from hourglass starting at (0,1): 2+3+4+0+3+2+1=15.

💡 Check that your code does not greedily pick first max but scans all hourglasses.

💡 Verify all hourglass sums are compared to find global max.

💡 Fix by iterating over all valid hourglass starting points and updating max sum.

Why it failed: Failing means greedy approach picking first max or partial scan. Fix by scanning all hourglass positions.

✓ Correctly finds global max hourglass sum, avoiding greedy trap.

t3_02corner

Input{"matrix":[[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1]]}

Expected7

⏱ Performance - must finish in 2000ms

All hourglasses have sum 7; code must return 7, not sum of all elements.

💡 Ensure you sum only hourglass pattern elements, not entire 3x3 blocks.

💡 Check indexing carefully to exclude non-hourglass elements.

💡 Fix by summing only the 7 specific hourglass positions per pattern.

Why it failed: Failing means summing entire 3x3 block instead of hourglass shape. Fix sum calculation to exclude middle row corners.

✓ Correctly sums only hourglass pattern elements.

t3_03corner

Input{"matrix":[[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15],[16,17,18,19,20],[21,22,23,24,25]]}

Expected133

⏱ Performance - must finish in 2000ms

Max hourglass sum is 99 from hourglass starting at (2,2): 13+14+15+19+23+24+25=99.

💡 Check for off-by-one errors in loop bounds when scanning hourglasses.

💡 Verify loops run from 0 to n-3 and 0 to m-3 inclusive.

💡 Fix loop conditions to include all valid hourglass starting points.

Why it failed: Failing means missing last valid hourglass due to loop bounds off-by-one. Fix loop conditions to i < n-2 and j < m-2.

✓ Correctly scans all hourglass positions including boundaries.

t4_01performance

Input{"matrix":[[1000,999,998,997,996,995,994,993,992,991,990,989,988,987,986,985,984,983,982,981,980,979,978,977,976,975,974,973,972,971,970,969,968,967,966,965,964,963,962,961,960,959,958,957,956,955,954,953,952,951,950,949,948,947,946,945,944,943,942,941,940,939,938,937,936,935,934,933,932,931,930,929,928,927,926,925,924,923,922,921,920,919,918,917,916,915,914,913,912,911,910,909,908,907,906,905,904,903,902,901],[900,899,898,897,896,895,894,893,892,891,890,889,888,887,886,885,884,883,882,881,880,879,878,877,876,875,874,873,872,871,870,869,868,867,866,865,864,863,862,861,860,859,858,857,856,855,854,853,852,851,850,849,848,847,846,845,844,843,842,841,840,839,838,837,836,835,834,833,832,831,830,829,828,827,826,825,824,823,822,821,820,819,818,817,816,815,814,813,812,811,810,809,808,807,806,805,804,803,802],[801,800,799,798,797,796,795,794,793,792,791,790,789,788,787,786,785,784,783,782,781,780,779,778,777,776,775,774,773,772,771,770,769,768,767,766,765,764,763,762,761,760,759,758,757,756,755,754,753,752,751,750,749,748,747,746,745,744,743,742,741,740,739,738,737,736,735,734,733,732,731,730,729,728,727,726,725,724,723,722,721,720,719,718,717,716,715,714,713,712,711,710,709,708,707,706,705,704,703,702],[701,700,699,698,697,696,695,694,693,692,691,690,689,688,687,686,685,684,683,682,681,680,679,678,677,676,675,674,673,672,671,670,669,668,667,666,665,664,663,662,661,660,659,658,657,656,655,654,653,652,651,650,649,648,647,646,645,644,643,642,641,640,639,638,637,636,635,634,633,632,631,630,629,628,627,626,625,624,623,622,621,620,619,618,617,616,615,614,613,612,611,610,609,608,607,606,605,604,603,602],[601,600,599,598,597,596,595,594,593,592,591,590,589,588,587,586,585,584,583,582,581,580,579,578,577,576,575,574,573,572,571,570,569,568,567,566,565,564,563,562,561,560,559,558,557,556,555,554,553,552,551,550,549,548,547,546,545,544,543,542,541,540,539,538,537,536,535,534,533,532,531,530,529,528,527,526,525,524,523,522,521,520,519,518,517,516,515,514,513,512,511,510,509,508,507,506,505,504,503,502],[501,500,499,498,497,496,495,494,493,492,491,490,489,488,487,486,485,484,483,482,481,480,479,478,477,476,475,474,473,472,471,470,469,468,467,466,465,464,463,462,461,460,459,458,457,456,455,454,453,452,451,450,449,448,447,446,445,444,443,442,441,440,439,438,437,436,435,434,433,432,431,430,429,428,427,426,425,424,423,422,421,420,419,418,417,416,415,414,413,412,411,410,409,408,407,406,405,404,403,402],[401,400,399,398,397,396,395,394,393,392,391,390,389,388,387,386,385,384,383,382,381,380,379,378,377,376,375,374,373,372,371,370,369,368,367,366,365,364,363,362,361,360,359,358,357,356,355,354,353,352,351,350,349,348,347,346,345,344,343,342,341,340,339,338,337,336,335,334,333,332,331,330,329,328,327,326,325,324,323,322,321,320,319,318,317,316,315,314,313,312,311,310,309,308,307,306,305,304,303,302],[301,300,299,298,297,296,295,294,293,292,291,290,289,288,287,286,285,284,283,282,281,280,279,278,277,276,275,274,273,272,271,270,269,268,267,266,265,264,263,262,261,260,259,258,257,256,255,254,253,252,251,250,249,248,247,246,245,244,243,242,241,240,239,238,237,236,235,234,233,232,231,230,229,228,227,226,225,224,223,222,221,220,219,218,217,216,215,214,213,212,211,210,209,208,207,206,205,204,203,202],[201,200,199,198,197,196,195,194,193,192,191,190,189,188,187,186,185,184,183,182,181,180,179,178,177,176,175,174,173,172,171,170,169,168,167,166,165,164,163,162,161,160,159,158,157,156,155,154,153,152,151,150,149,148,147,146,145,144,143,142,141,140,139,138,137,136,135,134,133,132,131,130,129,128,127,126,125,124,123,122,121,120,119,118,117,116,115,114,113,112,111,110,109,108,107,106,105,104,103,102],[101,100,99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2],[1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10,-11,-12,-13,-14,-15,-16,-17,-18,-19,-20,-21,-22,-23,-24,-25,-26,-27,-28,-29,-30,-31,-32,-33,-34,-35,-36,-37,-38,-39,-40,-41,-42,-43,-44,-45,-46,-47,-48,-49,-50,-51,-52,-53,-54,-55,-56,-57,-58,-59,-60,-61,-62,-63,-64,-65,-66,-67,-68,-69,-70,-71,-72,-73,-74,-75,-76,-77,-78,-79,-80,-81,-82,-83,-84,-85,-86,-87,-88,-89,-90,-91,-92,-93,-94,-95,-96,-97,-98]]}

Expectednull

⏱ Performance - must finish in 2000ms

Large 15x100 matrix (n=15, m=100) tests O(n*m) complexity; must complete within 2 seconds.

💡 Brute force is O(n*m) and should pass for n,m up to 1000.

💡 Avoid nested loops beyond hourglass pattern; no exponential complexity.

💡 Use direct summation of fixed 7 elements per hourglass.

Why it failed: TLE indicates algorithm is worse than O(n*m). Fix by using direct nested loops scanning all hourglass positions once.

✓ Algorithm runs in O(n*m) time confirming efficiency.

Practice

1. Given the following Python code for diagonal traversal, what is the final output when the input matrix is [[1,2,3],[4,5,6],[7,8,9]]?

easy

A. [1,4,2,3,5,7,8,6,9]

B. [1,2,4,7,5,3,6,8,9]

C. [1,2,3,4,5,6,7,8,9]

D. [1,2,4,5,3,6,7,8,9]

Solution

1. Step 1: Trace diagonal 0 (d=0)

   r_start=0, r_end=0, even diagonal -> traverse from r_end down to r_start: mat[0][0]=1

2. Step 2: Trace diagonal 1 (d=1)

   r_start=0, r_end=1, odd diagonal -> traverse from r_start up to r_end: mat[0][1]=2, mat[1][0]=4

3. Step 3: Trace diagonal 2 (d=2)

   r_start=0, r_end=2, even diagonal -> traverse from r_end down to r_start: mat[2][0]=7, mat[1][1]=5, mat[0][2]=3

4. Step 4: Trace diagonal 3 (d=3)

   r_start=1, r_end=2, odd diagonal -> traverse from r_start up to r_end: mat[1][2]=6, mat[2][1]=8

5. Step 5: Trace diagonal 4 (d=4)

   r_start=2, r_end=2, even diagonal -> traverse from r_end down to r_start: mat[2][2]=9

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Output matches expected zigzag diagonal order [OK]

Hint: Even diagonals traverse down, odd diagonals traverse up [OK]

Common Mistakes:

• Mixing traversal direction for even/odd diagonals

2. You are given a square matrix and asked to transform it so that rows become columns and columns become rows without using extra space. Which approach guarantees an optimal in-place solution?

easy

A. Use a brute force approach by creating a new matrix and copying elements accordingly.

B. Swap elements symmetrically across the diagonal only once, iterating over the upper triangle of the matrix.

C. Apply a greedy approach by swapping elements row-wise without considering the diagonal symmetry.

D. Use dynamic programming to store intermediate transposed states and build the final matrix.

Solution

1. Step 1: Understand the problem constraints

   The problem requires an in-place transpose of a square matrix, meaning no extra matrix can be used.

2. Step 2: Identify the correct approach

   Swapping elements symmetrically across the diagonal once (upper triangle only) ensures each pair is swapped exactly once, achieving in-place transpose efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Swapping only upper triangle elements avoids double swaps and extra space [OK]

Hint: Swap only upper triangle elements once [OK]

Common Mistakes:

• Using extra space unnecessarily
• Swapping elements twice by iterating entire matrix
• Ignoring diagonal symmetry leading to incorrect results

3. What is the time complexity of the in-place transpose algorithm for an n x n matrix that swaps elements only above the main diagonal?

medium

A. O(n)

B. O(n^3)

C. O(n^2 / 2)

D. O(n^2)

Solution

1. Step 1: Identify loops and iterations

   The outer loop runs n times, inner loop runs approximately n - i - 1 times, summing to about n(n-1)/2 swaps.

2. Step 2: Simplify complexity

   Ignoring constants and lower order terms, time complexity is O(n^2).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Quadratic time due to nested loops over matrix elements [OK]

Hint: Nested loops over n x n matrix -> O(n^2) [OK]

Common Mistakes:

• Confusing O(n^2 / 2) as different from O(n^2)
• Mistaking it for O(n^3) due to nested loops
• Assuming linear time due to skipping diagonal

4. Suppose you want to extend diagonal traversal to handle matrices where elements can be updated dynamically and you need to output the diagonal traversal multiple times efficiently. Which modification to the algorithm is most appropriate?

hard

A. Precompute and store all diagonals in separate lists to allow O(1) retrieval per traversal.

B. Use the original traversal code each time since it is already optimal with O(m*n) time.

C. Flatten the matrix into a 1D array and sort it to simulate diagonal traversal.

D. Maintain a segment tree per diagonal to support dynamic updates and queries efficiently.

Solution

1. Step 1: Understand the requirement for dynamic updates

   Repeated diagonal traversals with updates require efficient update and query support.

2. Step 2: Evaluate options for dynamic support

   Precomputing diagonals (A) is fast for static data but inefficient for updates. Original code (B) recomputes fully each time. Flattening and sorting (D) loses diagonal order and is inefficient.

3. Step 3: Use segment trees per diagonal

   Segment trees allow efficient updates and queries on each diagonal, enabling fast repeated traversals.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Segment trees balance update and query efficiency for dynamic diagonal traversal [OK]

Hint: Dynamic updates require data structures supporting fast queries [OK]

Common Mistakes:

• Assuming original code is always optimal for dynamic queries

5. Suppose you want to output the spiral order of a matrix but now the matrix can contain negative numbers and zero, and you want to skip all zeros during traversal. Which modification to the optimal boundary shrinking algorithm correctly handles this variant without revisiting elements or breaking order?

hard

A. Add a visited matrix to mark skipped zeros and continue traversal using direction vectors.

B. Modify the boundary shrinking algorithm to skip zeros during appending but still shrink boundaries normally.

C. Use a brute force nested loop with boundary checks and skip zeros when appending elements.

D. Traverse the matrix in spiral order but collect only non-zero elements, ignoring zeros without changing traversal.

Solution

1. Step 1: Understand the challenge of skipping zeros

   Skipping zeros means some elements are not appended, but traversal must still visit all cells exactly once without repeats.

2. Step 2: Why boundary shrinking alone fails

   Boundary shrinking assumes all elements are appended; skipping zeros breaks this assumption causing incorrect boundaries or missed elements.

3. Step 3: Using a visited matrix with direction vectors

   Tracking visited cells allows skipping zeros safely while continuing traversal correctly without revisiting or missing elements.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Visited matrix ensures correct traversal despite skipping zeros [OK]

Hint: Skipping elements breaks boundary assumptions; track visited cells [OK]

Common Mistakes:

• Skipping zeros but shrinking boundaries as usual causing missed elements
• Ignoring visited tracking leading to infinite loops or repeats
• Using brute force which is inefficient