Loading…

mediumArraysSometimes asked

Maximum Hourglass Sum

Q: How do you solve Maximum Hourglass Sum using the Baseline — Recompute the 3×3 Neighborhood with Conditionals approach?

When to use it: Mention it as the version that reads all 9 cells and skips the two sides — clunky but correct — then tighten it. For every valid top-left corner, walk the 3×3 neighborhood with two nested offsets and add each cell — except skip `(dr, dc) = (1, 0)` and `(1, 2)`, the two middle-side cells the hourglass excludes. **Why the corner stops at n−3.** A 3×3 block at `(r, c)` reads up to `(r+2, c+2)`. To stay inside an n×n grid you need `r+2 ≤ n−1`, i.e. `r ≤ n−3`, and likewise for `c`. That yields a `(n−2) × (n−2)` corner region — `(n−2)²` hourglasses. Hardcoding `4` (the 6×6 answer) is the classic generalization bug. **Why this version is clunky.** Reading all nine cells and excluding two with `if` checks works, but the conditional obscures the shape and risks excluding the wrong cells. It's a fine first pass to confirm correctness, but the explicit seven-term sum is clearer and equally fast. **Why `best` starts at −∞.** With values as low as −10⁶, an hourglass can sum well below zero and an entire grid can be negative. Initializing `best = 0` returns 0 on such a grid — a sum no hourglass produces. Use `Long.MIN_VALUE`/`float('-inf')`. Time complexity: O(n²). Space complexity: O(1).

Q: How do you solve Maximum Hourglass Sum using the Direct Mask Sum — Sliding Hourglass (Optimal) approach?

When to use it: The clean answer: write the 7-term sum explicitly and slide it across all (n−2)² corners. Express the hourglass sum as an explicit seven-term expression and evaluate it at every valid corner, keeping the maximum. **The mask as three bands.** `top = g[r][c] + g[r][c+1] + g[r][c+2]`, `mid = g[r+1][c+1]`, `bottom = g[r+2][c] + g[r+2][c+1] + g[r+2][c+2]`. Naming the bands makes the shape self-evident and the index offsets easy to audit — the most common source of bugs in this problem is a stray offset. **Why O(n²) is optimal.** There are `(n−2)²` hourglasses and each is a constant six additions, so the total is `Θ(n²)`. You can't do better than `Θ(n²)` because any correct answer must read essentially every cell at least once, and there are `n²` cells. A prefix sum would add machinery without lowering the asymptotic cost, because the mask is already tiny and fixed. **Why the bounds are length-based.** Writing the loop as `r + 2 < n` (rather than `r <= 4`) makes the code correct for any `n` and even adapts to rectangular grids if you bound rows and columns separately. This is the generalization the interviewer is checking for. **Why the sentinel matters again.** Same as before: an all-negative grid means the true maximum is negative, so the running max must start at `−∞`. This is the single most common wrong-answer cause and worth stating aloud. Time complexity: O(n²). Space complexity: O(1).

Arrays & Hashing · 47 of 83 · 7 min

Given an n × n grid of integers, an hourglass is the set of 7 cells in this shape anchored at a top-left corner (r, c):

a b c
  d
e f g

Compute the hourglass sum for every position where the shape fits inside the grid, and return the maximum hourglass sum. Sums may be negative.

In plain English

Same hourglass shape as the 6×6 problem, but the grid is now any n×n with n ≥ 3. The number of valid top-left corners grows to (n−2)², and we still sum the 7 masked cells at each corner and track the maximum. Negative sums are possible, so the running max must start at −∞.

Examples

Example 1

Input: n = 4, grid = 1 1 1 0 0 1 0 0 1 1 1 0 0 0 2 4
Output: 7
Note: Corners range over 0..1 in both axes (4 hourglasses). The corner (0,0) gives (1+1+1)+1+(1+1+1)=7, the maximum.

Example 2

Input: n = 3, grid = -1 -2 -3 -4 -5 -6 -7 -8 -9
Output: -35
Note: Only one hourglass: top = −1−2−3 = −6, mid = −5, bottom = −7−8−9 = −24, total −35. It's negative, so a 0-initialized max would return the wrong answer.

Constraints

3 ≤ n ≤ 1000
Grid is square (n × n)
-10⁶ ≤ grid[i][j] ≤ 10⁶
At least one hourglass exists (n ≥ 3)

Clarifying questions4First question: Is the grid guaranteed square?Explore questions

Q1.Is the grid guaranteed square?
Yes, n×n. For a general rectangular grid, the bounds become rows−2 and cols−2 independently.
Q2.Can hourglass sums be negative?
Yes. Initialize the running maximum to −∞ so an all-negative grid returns the least-negative sum, not 0.
Q3.How many hourglasses are there?
(n−2)². The corner ranges over rows 0..n−3 and columns 0..n−3. For n = 6 that's 16.
Q4.Is a prefix sum worth it here?
No. The mask is a fixed 7 cells, so each sum is constant work; the total O(n²) is already optimal.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Generalize the hourglass scan to any n×n grid. An hourglass is a 3×3 block minus its two middle-side cells (7 cells total). Slide the top-left corner over every position where a 3×3 block fits — rows 0..n−3 and columns 0..n−3 — sum the 7 masked cells, and keep the maximum. There are (n−2)² hourglasses, so the work is O(n²). Initialize the max to a very negative value because sums can be negative.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can generalize a fixed-grid trick to arbitrary n, derive the corner bounds from the mask footprint, and guard against the all-negative case with a proper sentinel.

Where candidates slip

Hardcoding 4 (the 6×6 count) as the loop bound instead of n−2, or starting the max at 0 and returning 0 on an all-negative grid.

How to stand out

Derive the bound (n−2)² from 'r+2 ≤ n−1', mention the mask is constant-size so re-summing is already optimal, and explicitly handle the negative-sum case.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Baseline — Recompute the 3×3 Neighborhood with Conditionals	`O(n²)`	`O(1)`	Mention it as the version that reads all 9 cells and skips the two sides — clunky but correct — then tighten it.	Read
2	Direct Mask Sum — Sliding Hourglass (Optimal)Optimal	`O(n²)`	`O(1)`	The clean answer: write the 7-term sum explicitly and slide it across all (n−2)² corners.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Generalized hourglass bounds

How to read it:The corner ranges over (n−2)×(n−2) positions for an n×n grid.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Baseline — Recompute the 3×3 Neighborhood with Conditionals

TimeO(n²)SpaceO(1)

Mention it as the version that reads all 9 cells and skips the two sides — clunky but correct — then tighten it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For each valid corner, you could loop the 3×3 block and add cells, skipping the two middle-side ones with a condition.

2Hint 2Explore hint

Which two cells inside the 3×3 are excluded from the hourglass?

3Hint 3Explore hint

Conditionals inside a tight loop work but obscure the shape — can you write the seven cells directly instead?

A · Core idea

For every valid top-left corner, walk the 3×3 neighborhood with two nested offsets and add each cell — except skip (dr, dc) = (1, 0) and (1, 2), the two middle-side cells the hourglass excludes.

Why the corner stops at n−3. A 3×3 block at (r, c) reads up to (r+2, c+2). To stay inside an n×n grid you need r+2 ≤ n−1, i.e. r ≤ n−3, and likewise for c. That yields a (n−2) × (n−2) corner region — (n−2)² hourglasses. Hardcoding 4 (the 6×6 answer) is the classic generalization bug.

Why this version is clunky. Reading all nine cells and excluding two with if checks works, but the conditional obscures the shape and risks excluding the wrong cells. It's a fine first pass to confirm correctness, but the explicit seven-term sum is clearer and equally fast.

Why `best` starts at −∞. With values as low as −10⁶, an hourglass can sum well below zero and an entire grid can be negative. Initializing best = 0 returns 0 on such a grid — a sum no hourglass produces. Use Long.MIN_VALUE/float('-inf').

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

the n=4 example grid

Interactive diagram

Why (n−2)² corners

corner (0,0)

Active call / nodeSupporting contextReturned stateNot active

r+2 ≤ n−1 forces r ≤ n−3; same for c.

Final result7

C · Code with teaching comments

Reference implementation previewpublic long maxHourglassSum(int[][] grid) { int n = grid.length; long best = Long.MIN_VALUE; for (int r = 0; r <= n - 3; r++) { for (int c = 0; c <= n - 3; c++) {Explore the full code

solution.javaJava

Baseline — Recompute the 3×3 Neighborhood with Conditionals — reference

2 teaching notes

1
public long maxHourglassSum(int[][] grid) {
2
    int n = grid.length;
3
    long best = Long.MIN_VALUE;
4
    // Corner stops at n−3 so grid[r+2] stays within the last row.
5
    for (int r = 0; r <= n - 3; r++) {
6
        for (int c = 0; c <= n - 3; c++) {
7
            long sum = 0;
8
            for (int dr = 0; dr < 3; dr++) {
9
                for (int dc = 0; dc < 3; dc++) {
10
                    // Skip the two middle-side cells to leave only the hourglass waist.
11
                    if (dr == 1 && (dc == 0 || dc == 2)) continue;
12
                    sum += grid[r + dr][c + dc];
13
                }
14
            }
15
            best = Math.max(best, sum);
16
        }
17
    }
18
    return best;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

Deriving the bound n−3 for the corner (from r+2 ≤ n−1) is the one piece that generalizes the 6×6 trick. Memorizing '16' fails the moment the grid size changes.

ComplexityO(n²) time, O(1) space — (n−2)² corners × a constant 9-cell visit each = O(n²); the skip conditions don't change the asymptotics.

E · Edge cases and pitfalls5n = 3 — Exactly one hourglass; the loops run once.Explore edge cases

Edge cases handled

n = 3Exactly one hourglass; the loops run once.
all-negative gridReturns the least-negative sum, never 0.

Pitfalls

Hardcoding 4 as the loop bound instead of n−2.
Excluding the wrong cells (e.g. corners) in the skip condition.
Initializing best to 0 — wrong on all-negative grids.

03.2

Approach 2 of 2 · Optimal

Direct Mask Sum — Sliding Hourglass (Optimal)

TimeO(n²)SpaceO(1)

The clean answer: write the 7-term sum explicitly and slide it across all (n−2)² corners.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Write the hourglass as three named bands: a top row of three, a single center, a bottom row of three.

2Hint 2Explore hint

Slide the corner over rows 0..n−3 and columns 0..n−3; each sum is the same expression with shifted indices.

3Hint 3Explore hint

Track the maximum as you go, starting from a very negative sentinel.

A · Core idea

Express the hourglass sum as an explicit seven-term expression and evaluate it at every valid corner, keeping the maximum.

The mask as three bands. top = g[r][c] + g[r][c+1] + g[r][c+2], mid = g[r+1][c+1], bottom = g[r+2][c] + g[r+2][c+1] + g[r+2][c+2]. Naming the bands makes the shape self-evident and the index offsets easy to audit — the most common source of bugs in this problem is a stray offset.

Why O(n²) is optimal. There are (n−2)² hourglasses and each is a constant six additions, so the total is Θ(n²). You can't do better than Θ(n²) because any correct answer must read essentially every cell at least once, and there are n² cells. A prefix sum would add machinery without lowering the asymptotic cost, because the mask is already tiny and fixed.

Why the bounds are length-based. Writing the loop as r + 2 < n (rather than r <= 4) makes the code correct for any n and even adapts to rectangular grids if you bound rows and columns separately. This is the generalization the interviewer is checking for.

Why the sentinel matters again. Same as before: an all-negative grid means the true maximum is negative, so the running max must start at −∞. This is the single most common wrong-answer cause and worth stating aloud.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

the n=4 example grid

Array state

top band

1 + 1 + 1 = 3

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result7

C · Code with teaching comments

solution.javaJava

Direct Mask Sum — Sliding Hourglass (Optimal) — optimal

2 teaching notes

1
public long maxHourglassSum(int[][] grid) {
2
    int n = grid.length;
3
    long best = Long.MIN_VALUE;
4
    // Length-based bound generalizes the corner range to any n.
5
    for (int r = 0; r + 2 < n; r++) {
6
        for (int c = 0; c + 2 < n; c++) {
7
            long sum = grid[r][c] + grid[r][c + 1] + grid[r][c + 2]
8
                     // The single waist cell — the only survivor of the middle row.
9
                     + grid[r + 1][c + 1]
10
                     + grid[r + 2][c] + grid[r + 2][c + 1] + grid[r + 2][c + 2];
11
            best = Math.max(best, sum);
12
        }
13
    }
14
    return best;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

When a fixed-shape mask slides over a grid, naming the mask's pieces (top/center/bottom bands) turns a bug-prone index soup into self-documenting code. The O(n²) bound is forced by the n² cells — there's nothing to optimize beyond clean enumeration.

ComplexityO(n²) time, O(1) space — (n−2)² corner positions, each a constant 6-addition sum → O(n²) time, O(1) extra space. With a fixed-size mask this is asymptotically optimal — every cell must be read at least once.

E · Edge cases and pitfalls5rectangular grid — Bound rows and cols separately (rows−2, cols−2); the band sum is unchanged.Explore edge cases

Edge cases handled

rectangular gridBound rows and cols separately (rows−2, cols−2); the band sum is unchanged.
n = 3Single hourglass; the loops execute exactly once.

Pitfalls

Reusing the 6×6 constant 16 or bound 4 for a general n.
Zero-initializing best.
Adding the middle-side cells and turning the mask into a full 3×3 sum.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long maxHourglassSum(int[][] grid) { int n = grid.length; long best = Long.MIN_VALUE; for (int r = 0; r + 2 < n; r++) { for (int c = 0; c + 2 < n; c++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Hardcoded grid size

Bounds tied to the 6×6 case break on any other n; the corner loop must derive from the grid length.

Explore the code comparison

Don't write this

for (int r = 0; r <= 3; r++) {
    for (int c = 0; c <= 3; c++) { /* ... */ }
}

Write this instead

for (int r = 0; r + 2 < n; r++) {
    for (int c = 0; c + 2 < n; c++) { /* ... */ }
}

Zero-initialized maximum

An all-negative grid has every hourglass sum below 0, so starting at 0 returns a value that never occurs.

Explore the code comparison

Don't write this

best = 0
# best = max(best, s)

Write this instead

best = float('-inf')
# best = max(best, s)

Full-block sum

Including the two middle-side cells overcounts; the hourglass is 7 cells, not 9.

Explore the code comparison

Don't write this

s = sum(grid[r+dr][c+dc] for dr in range(3) for dc in range(3))

Write this instead

s = (grid[r][c]+grid[r][c+1]+grid[r][c+2]
     + grid[r+1][c+1]
     + grid[r+2][c]+grid[r+2][c+1]+grid[r+2][c+2])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

3×3 hourglass mask slid across an n×n grid

Code pattern to memorize

best = -inf
for r in 0..n-3:
    for c in 0..n-3:
        s = g[r][c]+g[r][c+1]+g[r][c+2]
          + g[r+1][c+1]
          + g[r+2][c]+g[r+2][c+1]+g[r+2][c+2]
        best = max(best, s)

Rules to remember

1An n×n grid has (n−2)² hourglasses; the 6×6 special case gives 16.
2Iterate the corner over rows 0..n−3 and columns 0..n−3 so r+2 and c+2 stay in bounds.
3Initialize the running max to −∞, never 0 — an all-negative grid has every hourglass sum below 0.
4The mask is 7 cells: a full top row, the single center of the middle row, and a full bottom row.
5No prefix sum is needed — the mask is fixed at 7 cells, so each sum is O(1) and the total is O(n²).

Use this pattern when

A fixed-shape stencil (hourglass, plus, X) must be evaluated at every legal position in a grid
You need the max/min/best of that fixed pattern over an n×n matrix
The mask is small and fixed, so re-summing each position is already optimal

Choose another pattern when

The window is a variable-size rectangle whose sum updates incrementally → 2D prefix sums
You need many different submatrix sums → integral image / summed-area table
The mask is large relative to the grid → precompute row/partial sums to avoid re-adding

Interview takeaway

Sliding a fixed-shape mask over an n×n grid is 'enumerate every legal corner, sum the masked cells, keep the best' — O(n²) for a constant-size mask. The recurring traps are the corner bounds (n−2 per axis) and the negative initialization.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternFixed-shape mask over an n×n grid. Enumerate every legal top-left corner ((n−2)² of them), sum the masked cells, keep the best — O(n²), optimal for a constant-size mask. The traps are deriving the corner bounds from the grid size and the negative initialization.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Dynamic Array

Continue · Next problem

Missing Numbers

mediumArraysSometimes asked

Maximum Hourglass Sum

Arrays & Hashing · 47 of 83 · 7 min

Given an n × n grid of integers, an hourglass is the set of 7 cells in this shape anchored at a top-left corner (r, c):

a b c
  d
e f g

Compute the hourglass sum for every position where the shape fits inside the grid, and return the maximum hourglass sum. Sums may be negative.

In plain English

Examples

Example 1

Input: n = 4, grid = 1 1 1 0 0 1 0 0 1 1 1 0 0 0 2 4
Output: 7
Note: Corners range over 0..1 in both axes (4 hourglasses). The corner (0,0) gives (1+1+1)+1+(1+1+1)=7, the maximum.

Example 2

Input: n = 3, grid = -1 -2 -3 -4 -5 -6 -7 -8 -9
Output: -35
Note: Only one hourglass: top = −1−2−3 = −6, mid = −5, bottom = −7−8−9 = −24, total −35. It's negative, so a 0-initialized max would return the wrong answer.

Constraints

3 ≤ n ≤ 1000
Grid is square (n × n)
-10⁶ ≤ grid[i][j] ≤ 10⁶
At least one hourglass exists (n ≥ 3)

Clarifying questions4First question: Is the grid guaranteed square?Explore questions

Q1.Is the grid guaranteed square?
Yes, n×n. For a general rectangular grid, the bounds become rows−2 and cols−2 independently.
Q2.Can hourglass sums be negative?
Yes. Initialize the running maximum to −∞ so an all-negative grid returns the least-negative sum, not 0.
Q3.How many hourglasses are there?
(n−2)². The corner ranges over rows 0..n−3 and columns 0..n−3. For n = 6 that's 16.
Q4.Is a prefix sum worth it here?
No. The mask is a fixed 7 cells, so each sum is constant work; the total O(n²) is already optimal.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can generalize a fixed-grid trick to arbitrary n, derive the corner bounds from the mask footprint, and guard against the all-negative case with a proper sentinel.

Where candidates slip

Hardcoding 4 (the 6×6 count) as the loop bound instead of n−2, or starting the max at 0 and returning 0 on an all-negative grid.

How to stand out

Derive the bound (n−2)² from 'r+2 ≤ n−1', mention the mask is constant-size so re-summing is already optimal, and explicitly handle the negative-sum case.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Baseline — Recompute the 3×3 Neighborhood with Conditionals	`O(n²)`	`O(1)`	Mention it as the version that reads all 9 cells and skips the two sides — clunky but correct — then tighten it.	Read
2	Direct Mask Sum — Sliding Hourglass (Optimal)Optimal	`O(n²)`	`O(1)`	The clean answer: write the 7-term sum explicitly and slide it across all (n−2)² corners.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Generalized hourglass bounds

How to read it:The corner ranges over (n−2)×(n−2) positions for an n×n grid.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Baseline — Recompute the 3×3 Neighborhood with Conditionals

TimeO(n²)SpaceO(1)

Mention it as the version that reads all 9 cells and skips the two sides — clunky but correct — then tighten it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For each valid corner, you could loop the 3×3 block and add cells, skipping the two middle-side ones with a condition.

2Hint 2Explore hint

Which two cells inside the 3×3 are excluded from the hourglass?

3Hint 3Explore hint

Conditionals inside a tight loop work but obscure the shape — can you write the seven cells directly instead?

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

the n=4 example grid

Interactive diagram

Why (n−2)² corners

corner (0,0)

Active call / nodeSupporting contextReturned stateNot active

r+2 ≤ n−1 forces r ≤ n−3; same for c.

Final result7

C · Code with teaching comments

solution.javaJava

Baseline — Recompute the 3×3 Neighborhood with Conditionals — reference

2 teaching notes

1
public long maxHourglassSum(int[][] grid) {
2
    int n = grid.length;
3
    long best = Long.MIN_VALUE;
4
    // Corner stops at n−3 so grid[r+2] stays within the last row.
5
    for (int r = 0; r <= n - 3; r++) {
6
        for (int c = 0; c <= n - 3; c++) {
7
            long sum = 0;
8
            for (int dr = 0; dr < 3; dr++) {
9
                for (int dc = 0; dc < 3; dc++) {
10
                    // Skip the two middle-side cells to leave only the hourglass waist.
11
                    if (dr == 1 && (dc == 0 || dc == 2)) continue;
12
                    sum += grid[r + dr][c + dc];
13
                }
14
            }
15
            best = Math.max(best, sum);
16
        }
17
    }
18
    return best;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

Deriving the bound n−3 for the corner (from r+2 ≤ n−1) is the one piece that generalizes the 6×6 trick. Memorizing '16' fails the moment the grid size changes.

ComplexityO(n²) time, O(1) space — (n−2)² corners × a constant 9-cell visit each = O(n²); the skip conditions don't change the asymptotics.

E · Edge cases and pitfalls5n = 3 — Exactly one hourglass; the loops run once.Explore edge cases

Edge cases handled

n = 3Exactly one hourglass; the loops run once.
all-negative gridReturns the least-negative sum, never 0.

Pitfalls

Hardcoding 4 as the loop bound instead of n−2.
Excluding the wrong cells (e.g. corners) in the skip condition.
Initializing best to 0 — wrong on all-negative grids.

03.2

Approach 2 of 2 · Optimal

Direct Mask Sum — Sliding Hourglass (Optimal)

TimeO(n²)SpaceO(1)

The clean answer: write the 7-term sum explicitly and slide it across all (n−2)² corners.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Write the hourglass as three named bands: a top row of three, a single center, a bottom row of three.

2Hint 2Explore hint

Slide the corner over rows 0..n−3 and columns 0..n−3; each sum is the same expression with shifted indices.

3Hint 3Explore hint

Track the maximum as you go, starting from a very negative sentinel.

A · Core idea

Express the hourglass sum as an explicit seven-term expression and evaluate it at every valid corner, keeping the maximum.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

the n=4 example grid

Array state

top band

1 + 1 + 1 = 3

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result7

C · Code with teaching comments

solution.javaJava

Direct Mask Sum — Sliding Hourglass (Optimal) — optimal

2 teaching notes

1
public long maxHourglassSum(int[][] grid) {
2
    int n = grid.length;
3
    long best = Long.MIN_VALUE;
4
    // Length-based bound generalizes the corner range to any n.
5
    for (int r = 0; r + 2 < n; r++) {
6
        for (int c = 0; c + 2 < n; c++) {
7
            long sum = grid[r][c] + grid[r][c + 1] + grid[r][c + 2]
8
                     // The single waist cell — the only survivor of the middle row.
9
                     + grid[r + 1][c + 1]
10
                     + grid[r + 2][c] + grid[r + 2][c + 1] + grid[r + 2][c + 2];
11
            best = Math.max(best, sum);
12
        }
13
    }
14
    return best;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5rectangular grid — Bound rows and cols separately (rows−2, cols−2); the band sum is unchanged.Explore edge cases

Edge cases handled

rectangular gridBound rows and cols separately (rows−2, cols−2); the band sum is unchanged.
n = 3Single hourglass; the loops execute exactly once.

Pitfalls

Reusing the 6×6 constant 16 or bound 4 for a general n.
Zero-initializing best.
Adding the middle-side cells and turning the mask into a full 3×3 sum.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Hardcoded grid size

Bounds tied to the 6×6 case break on any other n; the corner loop must derive from the grid length.

Explore the code comparison

Don't write this

for (int r = 0; r <= 3; r++) {
    for (int c = 0; c <= 3; c++) { /* ... */ }
}

Write this instead

for (int r = 0; r + 2 < n; r++) {
    for (int c = 0; c + 2 < n; c++) { /* ... */ }
}

Zero-initialized maximum

An all-negative grid has every hourglass sum below 0, so starting at 0 returns a value that never occurs.

Explore the code comparison

Don't write this

best = 0
# best = max(best, s)

Write this instead

best = float('-inf')
# best = max(best, s)

Full-block sum

Including the two middle-side cells overcounts; the hourglass is 7 cells, not 9.

Explore the code comparison

Don't write this

s = sum(grid[r+dr][c+dc] for dr in range(3) for dc in range(3))

Write this instead

s = (grid[r][c]+grid[r][c+1]+grid[r][c+2]
     + grid[r+1][c+1]
     + grid[r+2][c]+grid[r+2][c+1]+grid[r+2][c+2])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

3×3 hourglass mask slid across an n×n grid

Code pattern to memorize

best = -inf
for r in 0..n-3:
    for c in 0..n-3:
        s = g[r][c]+g[r][c+1]+g[r][c+2]
          + g[r+1][c+1]
          + g[r+2][c]+g[r+2][c+1]+g[r+2][c+2]
        best = max(best, s)

Rules to remember

1An n×n grid has (n−2)² hourglasses; the 6×6 special case gives 16.
2Iterate the corner over rows 0..n−3 and columns 0..n−3 so r+2 and c+2 stay in bounds.
3Initialize the running max to −∞, never 0 — an all-negative grid has every hourglass sum below 0.
4The mask is 7 cells: a full top row, the single center of the middle row, and a full bottom row.
5No prefix sum is needed — the mask is fixed at 7 cells, so each sum is O(1) and the total is O(n²).

Use this pattern when

A fixed-shape stencil (hourglass, plus, X) must be evaluated at every legal position in a grid
You need the max/min/best of that fixed pattern over an n×n matrix
The mask is small and fixed, so re-summing each position is already optimal

Choose another pattern when

The window is a variable-size rectangle whose sum updates incrementally → 2D prefix sums
You need many different submatrix sums → integral image / summed-area table
The mask is large relative to the grid → precompute row/partial sums to avoid re-adding

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Dynamic Array

Continue · Next problem

Missing Numbers