Loading…

mediumArraysFrequently asked

2D Array - DS

Q: How do you solve 2D Array - DS using the Brute Force — Re-check Every Cell of Every 3×3 Block approach?

When to use it: Mention it to show you understand why the smarter version isn't really needed here, then move on quickly. Walk the top-left corner over every position where a full 3×3 block fits, then sum the 7 hourglass cells of that block directly. **Why the corner stops at row 3 and column 3.** A 3×3 block anchored at `(r, c)` reads cells up to `(r+2, c+2)`. For those to stay inside a 6×6 grid you need `r+2 ≤ 5` and `c+2 ≤ 5`, i.e. `r ≤ 3` and `c ≤ 3`. So the corner ranges over a 4×4 region: 4 rows × 4 columns = 16 hourglasses. Run the corner to row 5 and you index `arr[7]`, which is out of bounds. **Why we only touch 7 cells.** The hourglass excludes `arr[r+1][c]` and `arr[r+1][c+2]` — the left and right of the middle row. Only the center `arr[r+1][c+1]` survives. Reading all 9 and subtracting the two would also work, but it's clearer to sum exactly the 7 you want. **Why `best` starts negative.** With values down to −9, an hourglass can sum as low as −63, and an entire grid can be negative. If you initialize `best = 0`, a fully-negative grid returns 0 — a sum that never actually occurs. Start at something like `Integer.MIN_VALUE` (Java) or `float('-inf')` (Python). Time complexity: O(1). Space complexity: O(1).

Q: How do you solve 2D Array - DS using the Constant Pass — Closed-Form Over 16 Hourglasses (Optimal) approach?

When to use it: This is the clean answer: state there are 16 fixed hourglasses, sum each with the closed-form mask, keep the max. For a fixed-size grid the optimal solution *is* the direct enumeration — there's nothing asymptotically to improve. The value of treating it as 'optimal' is recognizing the structure so you write tight, correct code. **The mask as a closed form.** Every hourglass sum is `top + mid + bottom` where `top = arr[r][c] + arr[r][c+1] + arr[r][c+2]`, `mid = arr[r+1][c+1]`, and `bottom = arr[r+2][c] + arr[r+2][c+1] + arr[r+2][c+2]`. Writing it as three named pieces makes the shape obvious and the off-by-one mistakes visible. **Why no prefix sum helps.** A 2D prefix-sum array shines when you query many overlapping rectangles of varying size. Here the shape is fixed and tiny (7 cells), and there are only 16 queries, so building a prefix table costs more than it saves. Recognizing when *not* to add machinery is part of the answer. **Generalizing to n×n.** If the grid were n×n, the corner would range over rows `0..n−3` and columns `0..n−3`, giving `(n−2)²` hourglasses and `O(n²)` total work. The 6×6 case is just `(6−2)² = 16`. Mentioning this generalization signals you understand the bounds rather than memorizing 16. Time complexity: O(1). Space complexity: O(1).

Arrays & Hashing · 42 of 83 · 7 min

Given a 6×6 2D array arr, an hourglass is a subset of values with indices falling in this pattern within the array:

a b c
  d
e f g

There are 16 hourglasses in the array. Calculate the hourglass sum for every hourglass, then return the maximum hourglass sum.

An hourglass sum may be negative — at least one hourglass always exists.

In plain English

The grid is fixed at 6×6. An hourglass is 7 specific cells: a full top row of 3, a single middle cell directly below the center, and a full bottom row of 3. Slide the top-left corner over the 4×4 region of valid corners, sum the 7 masked cells at each position, and report the largest sum.

Examples

Example 1

Input: arr = 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 2 4 4 0 0 0 0 2 0 0 0 0 1 2 4 0
Output: 19
Note: The hourglass with top-left at (3,2) is 2 4 4 / 2 / 1 2 4 = (2+4+4)+(2)+(1+2+4) = 19, the maximum.

Example 2

Input: arr = -1 -1 0 -9 -2 -2 -2 -1 -6 -8 -2 -5 -1 -1 -1 -2 -3 -4 -1 -9 -2 -4 -4 -5 -7 -3 -3 -2 -9 -9 -1 -3 -1 -2 -4 -5
Output: -6
Note: Every hourglass is negative; the least-negative sum is −6. This is why you cannot start the max at 0.

Constraints

arr is always 6×6
-9 ≤ arr[i][j] ≤ 9
0 ≤ i, j ≤ 5
Exactly 16 hourglasses exist

Clarifying questions4First question: Is the grid always exactly 6×6?Explore questions

Q1.Is the grid always exactly 6×6?
Yes for the classic problem — that's why there are exactly 16 hourglasses. If it were n×n, the corner would range over (n−2)×(n−2) positions.
Q2.Can hourglass sums be negative?
Yes. Values range from −9 to 9, so an all-negative hourglass is possible. Initialize the running max to a very negative number, not 0.
Q3.Is the hourglass the full 3×3 block?
No. It excludes the two middle-side cells — only the center of the middle row is included. That's 7 cells, not 9.
Q4.Do I need the location of the best hourglass or just the sum?
Just the maximum sum for this problem.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

You're given a fixed 6×6 grid and must return the maximum hourglass sum. An hourglass is the 7 cells in a 3×3 block minus the two middle-side cells. There are exactly 16 hourglass positions (top-left corner ranges over rows 0–3 and columns 0–3). Sum each one with a closed-form expression and track the max — no nested scanning of each block needed.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can translate a visual shape into exact index offsets, get the loop bounds right so you never read out of bounds, and remember that an all-negative grid means `best` can't start at 0.

Where candidates slip

Initializing the running max to 0, which returns 0 on a grid where every hourglass sum is negative. Or looping the corner over 0..5 and indexing g[r+2] out of bounds.

How to stand out

Say up front 'the corner ranges over a 4×4 region, so there are exactly 16 hourglasses, and the work is constant'. Name the excluded cells explicitly so the interviewer knows you read the shape, not a full 3×3.

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	Brute Force — Re-check Every Cell of Every 3×3 Block	`O(1)`	`O(1)`	Mention it to show you understand why the smarter version isn't really needed here, then move on quickly.	Read
2	Constant Pass — Closed-Form Over 16 Hourglasses (Optimal)Optimal	`O(1)`	`O(1)`	This is the clean answer: state there are 16 fixed hourglasses, sum each with the closed-form mask, keep the max.	Read

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

The hourglass mask over the grid

How to read it:The corner (r, c) ranges over rows 0–3 and columns 0–3, giving 16 positions. The middle-side cells are never read.

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

Brute Force — Re-check Every Cell of Every 3×3 Block

TimeO(1)SpaceO(1)

Mention it to show you understand why the smarter version isn't really needed here, then move on quickly.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

How many top-left corners give a valid 3×3 block inside a 6×6 grid? Count the rows and columns the corner can sit on.

2Hint 2Explore hint

For each block, you only need 7 of its 9 cells. Which two do you skip?

3Hint 3Explore hint

Add up the 7 cells, compare against the best so far, and remember to start the best at a negative value.

A · Core idea

Walk the top-left corner over every position where a full 3×3 block fits, then sum the 7 hourglass cells of that block directly.

Why the corner stops at row 3 and column 3. A 3×3 block anchored at (r, c) reads cells up to (r+2, c+2). For those to stay inside a 6×6 grid you need r+2 ≤ 5 and c+2 ≤ 5, i.e. r ≤ 3 and c ≤ 3. So the corner ranges over a 4×4 region: 4 rows × 4 columns = 16 hourglasses. Run the corner to row 5 and you index arr[7], which is out of bounds.

Why we only touch 7 cells. The hourglass excludes arr[r+1][c] and arr[r+1][c+2] — the left and right of the middle row. Only the center arr[r+1][c+1] survives. Reading all 9 and subtracting the two would also work, but it's clearer to sum exactly the 7 you want.

Why `best` starts negative. With values down to −9, an hourglass can sum as low as −63, and an entire grid can be negative. If you initialize best = 0, a fully-negative grid returns 0 — a sum that never actually occurs. Start at something like Integer.MIN_VALUE (Java) or float('-inf') (Python).

B · Visual dry run

Interactive dry run

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

the first example grid

Interactive diagram

Why the corner range is 4×4

corner (0,0)

Active call / nodeSupporting contextReturned stateNot active

r+2 ≤ 5 forces r ≤ 3; the same logic bounds c. Hence 16 positions.

Final result19

C · Code with teaching comments

Reference implementation previewpublic int hourglassSum(int[][] arr) { int best = Integer.MIN_VALUE; for (int r = 0; r <= 3; r++) { for (int c = 0; c <= 3; c++) { int top = arr[r][c] + arr[r][c + 1] + arr[r][c + 2];Explore the full code

solution.javaJava

Brute Force — Re-check Every Cell of Every 3×3 Block — reference

3 teaching notes

1
public int hourglassSum(int[][] arr) {
2
    // Start negative — a grid of all −9s has every hourglass sum below 0, and 0 would
3
    // be a wrong answer.
4
    int best = Integer.MIN_VALUE;
5
    // The corner stops at row 3 so arr[r+2] never exceeds index 5.
6
    for (int r = 0; r <= 3; r++) {
7
        for (int c = 0; c <= 3; c++) {
8
            int top = arr[r][c] + arr[r][c + 1] + arr[r][c + 2];
9
            // Only the center of the middle row — the two side cells are excluded by
10
            // the hourglass shape.
11
            int mid = arr[r + 1][c + 1];
12
            int bottom = arr[r + 2][c] + arr[r + 2][c + 1] + arr[r + 2][c + 2];
13
            best = Math.max(best, top + mid + bottom);
14
        }
15
    }
16
    return best;
17
}

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

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

On a fixed 6×6 grid this 'brute force' is already optimal — the work is a constant 16 hourglasses. The lesson isn't the algorithm; it's getting the loop bounds and the negative initialization right.

ComplexityO(1) time, O(1) space — The grid is fixed at 6×6, so there are a constant 16 hourglasses and each costs a constant 6 additions. Everything here is O(1) — the 'brute' label only means 'no precomputation'.

E · Edge cases and pitfalls5all-negative 6×6 grid — Returns the least-negative hourglass sum (e.g. −6), never 0.Explore edge cases

Edge cases handled

all-negative 6×6 gridReturns the least-negative hourglass sum (e.g. −6), never 0.
grid where the best hourglass is at a corner like (0,0) or (3,3)Bounds 0..3 include every corner, so edge hourglasses are still considered.

Pitfalls

Initializing best to 0 — wrong on all-negative grids.
Looping the corner to 5 instead of 3 — reads arr[6] or arr[r][6] out of bounds.
Summing all 9 cells of the 3×3 block instead of the 7 hourglass cells.

03.2

Approach 2 of 2 · Optimal

Constant Pass — Closed-Form Over 16 Hourglasses (Optimal)

TimeO(1)SpaceO(1)

This is the clean answer: state there are 16 fixed hourglasses, sum each with the closed-form mask, keep the max.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Since the grid size is fixed, the number of hourglasses is fixed too. What's that number?

2Hint 2Explore hint

Each hourglass sum is the same expression with shifted indices — write it once, parameterized by the corner (r, c).

3Hint 3Explore hint

You never need to revisit a cell or store partial sums; one direct sum per corner is already constant total work.

A · Core idea

For a fixed-size grid the optimal solution is the direct enumeration — there's nothing asymptotically to improve. The value of treating it as 'optimal' is recognizing the structure so you write tight, correct code.

The mask as a closed form. Every hourglass sum is top + mid + bottom where top = arr[r][c] + arr[r][c+1] + arr[r][c+2], mid = arr[r+1][c+1], and bottom = arr[r+2][c] + arr[r+2][c+1] + arr[r+2][c+2]. Writing it as three named pieces makes the shape obvious and the off-by-one mistakes visible.

Why no prefix sum helps. A 2D prefix-sum array shines when you query many overlapping rectangles of varying size. Here the shape is fixed and tiny (7 cells), and there are only 16 queries, so building a prefix table costs more than it saves. Recognizing when not to add machinery is part of the answer.

Generalizing to n×n. If the grid were n×n, the corner would range over rows 0..n−3 and columns 0..n−3, giving (n−2)² hourglasses and O(n²) total work. The 6×6 case is just (6−2)² = 16. Mentioning this generalization signals you understand the bounds rather than memorizing 16.

B · Visual dry run

Interactive dry run

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

the first example grid

Array state

top band

2 + 4 + 4 = 10

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result19

C · Code with teaching comments

solution.javaJava

Constant Pass — Closed-Form Over 16 Hourglasses (Optimal) — optimal

2 teaching notes

1
public int hourglassSum(int[][] arr) {
2
    int best = Integer.MIN_VALUE;
3
    // Bound written as r+2 < length so it stays correct if the grid is generalized
4
    // beyond 6×6.
5
    for (int r = 0; r + 2 < arr.length; r++) {
6
        for (int c = 0; c + 2 < arr[r].length; c++) {
7
            int sum = arr[r][c] + arr[r][c + 1] + arr[r][c + 2]
8
                    // The single center cell of the middle row — the waist of the
9
                    // hourglass.
10
                    + arr[r + 1][c + 1]
11
                    + arr[r + 2][c] + arr[r + 2][c + 1] + arr[r + 2][c + 2];
12
            best = Math.max(best, sum);
13
        }
14
    }
15
    return best;
16
}

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

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

The trade here is conceptual, not computational: name the three bands of the mask (top, center, bottom) so the index offsets are self-documenting. That single habit kills the off-by-one bugs that sink most attempts at this problem.

ComplexityO(1) time, O(1) space — 16 hourglasses × 6 additions = 96 additions regardless of input. Constant time, constant space.

E · Edge cases and pitfalls5n×n grid with n > 6 — The length-based bounds (rows−2, cols−2) handle any n ≥ 3 with no code change.Explore edge cases

Edge cases handled

n×n grid with n > 6The length-based bounds (rows−2, cols−2) handle any n ≥ 3 with no code change.
n = 3 gridExactly one hourglass; the loops run once and return its sum.

Pitfalls

Hardcoding 4 as the loop bound, then breaking when asked to generalize to n×n.
Forgetting the negative initialization — the most common wrong-answer cause.
Including the middle-side cells, turning the hourglass into a full block sum.

Practice

Try the solution yourself

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

Editable code previewpublic int hourglassSum(int[][] arr) { int best = Integer.MIN_VALUE; for (int r = 0; r + 2 < arr.length; r++) { for (int c = 0; c + 2 < arr[r].length; c++) { int sum = arr[r][c] + arr[r][c + 1] + arr[r][c + 2]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.

Zero-initialized maximum

On a grid where every hourglass sum is negative, starting at 0 returns 0 — a value that no hourglass actually produces.

Explore the code comparison

Don't write this

int best = 0;
// ... best = Math.max(best, sum);

Write this instead

int best = Integer.MIN_VALUE;
// ... best = Math.max(best, sum);

Out-of-bounds corner range

Running the corner over 0..5 makes arr[r+2] reach index 7 — an ArrayIndexOutOfBoundsException.

Explore the code comparison

Don't write this

for (int r = 0; r <= 5; r++) {
    for (int c = 0; c <= 5; c++) {
        int sum = arr[r + 2][c + 2] + /* ... */;
    }
}

Write this instead

for (int r = 0; r + 2 < arr.length; r++) {
    for (int c = 0; c + 2 < arr[r].length; c++) {
        int sum = arr[r + 2][c + 2] + /* ... */;
    }
}

Summing the full block

Adding arr[r+1][c] and arr[r+1][c+2] turns the hourglass into a 9-cell square and overcounts.

Explore the code comparison

Don't write this

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

Write this instead

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Fixed-size mask slid over a bounded grid

Code pattern to memorize

for r in 0..3:
    for c in 0..3:
        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]
        best = max(best, top + mid + bottom)

Rules to remember

1There are exactly 16 hourglasses in a 6×6 grid: 4 valid top rows × 4 valid left columns.
2Initialize best to a very negative value, not 0 — sums can be negative when all 7 cells are negative.
3The hourglass is not a full 3×3 block. The two middle-side cells g[r+1][c] and g[r+1][c+2] are excluded.
4Iterate the top-left corner only over rows 0..3 and columns 0..3 so r+2 and c+2 stay in bounds.
5Sum the 7 cells directly — there's no benefit to a prefix-sum here because the mask is tiny and fixed.

Use this pattern when

A fixed-shape stencil (hourglass, plus, cross) slides over a bounded grid
The grid dimensions are constant, so total work is a constant number of fixed-cost sums
You need the max/min of a small fixed pattern over every legal position

Choose another pattern when

The window is a variable-size rectangle whose sum changes incrementally → 2D prefix sums
You need every subrectangle sum, not one fixed shape → integral image
The grid is huge and the mask is large → precompute partial sums instead of re-summing

Interview takeaway

When a fixed-shape mask slides over a bounded grid, the whole problem is 'enumerate every legal top-left corner, sum the masked cells, keep the best'. The only traps are the bounds (16 positions, not 36) and the negative-init for `best`.

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 a bounded grid. Enumerate every legal top-left corner, sum the masked cells, keep the best. The recurring traps are the bounds (count the valid corners) and the negative initialization. Generalizes to plus/cross stencils and to n×n grids.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Rabin–Karp Substring Search (Rolling Hash)

Continue · Next problem

Array Manipulation

mediumArraysFrequently asked

2D Array - DS

Arrays & Hashing · 42 of 83 · 7 min

Given a 6×6 2D array arr, an hourglass is a subset of values with indices falling in this pattern within the array:

a b c
  d
e f g

There are 16 hourglasses in the array. Calculate the hourglass sum for every hourglass, then return the maximum hourglass sum.

An hourglass sum may be negative — at least one hourglass always exists.

In plain English

Examples

Example 1

Input: arr = 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 2 4 4 0 0 0 0 2 0 0 0 0 1 2 4 0
Output: 19
Note: The hourglass with top-left at (3,2) is 2 4 4 / 2 / 1 2 4 = (2+4+4)+(2)+(1+2+4) = 19, the maximum.

Example 2

Input: arr = -1 -1 0 -9 -2 -2 -2 -1 -6 -8 -2 -5 -1 -1 -1 -2 -3 -4 -1 -9 -2 -4 -4 -5 -7 -3 -3 -2 -9 -9 -1 -3 -1 -2 -4 -5
Output: -6
Note: Every hourglass is negative; the least-negative sum is −6. This is why you cannot start the max at 0.

Constraints

arr is always 6×6
-9 ≤ arr[i][j] ≤ 9
0 ≤ i, j ≤ 5
Exactly 16 hourglasses exist

Clarifying questions4First question: Is the grid always exactly 6×6?Explore questions

Q1.Is the grid always exactly 6×6?
Yes for the classic problem — that's why there are exactly 16 hourglasses. If it were n×n, the corner would range over (n−2)×(n−2) positions.
Q2.Can hourglass sums be negative?
Yes. Values range from −9 to 9, so an all-negative hourglass is possible. Initialize the running max to a very negative number, not 0.
Q3.Is the hourglass the full 3×3 block?
No. It excludes the two middle-side cells — only the center of the middle row is included. That's 7 cells, not 9.
Q4.Do I need the location of the best hourglass or just the sum?
Just the maximum sum for this problem.

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 translate a visual shape into exact index offsets, get the loop bounds right so you never read out of bounds, and remember that an all-negative grid means `best` can't start at 0.

Where candidates slip

Initializing the running max to 0, which returns 0 on a grid where every hourglass sum is negative. Or looping the corner over 0..5 and indexing g[r+2] out of bounds.

How to stand out

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	Brute Force — Re-check Every Cell of Every 3×3 Block	`O(1)`	`O(1)`	Mention it to show you understand why the smarter version isn't really needed here, then move on quickly.	Read
2	Constant Pass — Closed-Form Over 16 Hourglasses (Optimal)Optimal	`O(1)`	`O(1)`	This is the clean answer: state there are 16 fixed hourglasses, sum each with the closed-form mask, keep the max.	Read

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

The hourglass mask over the grid

How to read it:The corner (r, c) ranges over rows 0–3 and columns 0–3, giving 16 positions. The middle-side cells are never read.

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

Brute Force — Re-check Every Cell of Every 3×3 Block

TimeO(1)SpaceO(1)

Mention it to show you understand why the smarter version isn't really needed here, then move on quickly.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

How many top-left corners give a valid 3×3 block inside a 6×6 grid? Count the rows and columns the corner can sit on.

2Hint 2Explore hint

For each block, you only need 7 of its 9 cells. Which two do you skip?

3Hint 3Explore hint

Add up the 7 cells, compare against the best so far, and remember to start the best at a negative value.

A · Core idea

Walk the top-left corner over every position where a full 3×3 block fits, then sum the 7 hourglass cells of that block directly.

B · Visual dry run

Interactive dry run

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

the first example grid

Interactive diagram

Why the corner range is 4×4

corner (0,0)

Active call / nodeSupporting contextReturned stateNot active

r+2 ≤ 5 forces r ≤ 3; the same logic bounds c. Hence 16 positions.

Final result19

C · Code with teaching comments

solution.javaJava

Brute Force — Re-check Every Cell of Every 3×3 Block — reference

3 teaching notes

1
public int hourglassSum(int[][] arr) {
2
    // Start negative — a grid of all −9s has every hourglass sum below 0, and 0 would
3
    // be a wrong answer.
4
    int best = Integer.MIN_VALUE;
5
    // The corner stops at row 3 so arr[r+2] never exceeds index 5.
6
    for (int r = 0; r <= 3; r++) {
7
        for (int c = 0; c <= 3; c++) {
8
            int top = arr[r][c] + arr[r][c + 1] + arr[r][c + 2];
9
            // Only the center of the middle row — the two side cells are excluded by
10
            // the hourglass shape.
11
            int mid = arr[r + 1][c + 1];
12
            int bottom = arr[r + 2][c] + arr[r + 2][c + 1] + arr[r + 2][c + 2];
13
            best = Math.max(best, top + mid + bottom);
14
        }
15
    }
16
    return best;
17
}

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

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

E · Edge cases and pitfalls5all-negative 6×6 grid — Returns the least-negative hourglass sum (e.g. −6), never 0.Explore edge cases

Edge cases handled

all-negative 6×6 gridReturns the least-negative hourglass sum (e.g. −6), never 0.
grid where the best hourglass is at a corner like (0,0) or (3,3)Bounds 0..3 include every corner, so edge hourglasses are still considered.

Pitfalls

Initializing best to 0 — wrong on all-negative grids.
Looping the corner to 5 instead of 3 — reads arr[6] or arr[r][6] out of bounds.
Summing all 9 cells of the 3×3 block instead of the 7 hourglass cells.

03.2

Approach 2 of 2 · Optimal

Constant Pass — Closed-Form Over 16 Hourglasses (Optimal)

TimeO(1)SpaceO(1)

This is the clean answer: state there are 16 fixed hourglasses, sum each with the closed-form mask, keep the max.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Since the grid size is fixed, the number of hourglasses is fixed too. What's that number?

2Hint 2Explore hint

Each hourglass sum is the same expression with shifted indices — write it once, parameterized by the corner (r, c).

3Hint 3Explore hint

You never need to revisit a cell or store partial sums; one direct sum per corner is already constant total work.

A · Core idea

B · Visual dry run

Interactive dry run

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

the first example grid

Array state

top band

2 + 4 + 4 = 10

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result19

C · Code with teaching comments

solution.javaJava

Constant Pass — Closed-Form Over 16 Hourglasses (Optimal) — optimal

2 teaching notes

1
public int hourglassSum(int[][] arr) {
2
    int best = Integer.MIN_VALUE;
3
    // Bound written as r+2 < length so it stays correct if the grid is generalized
4
    // beyond 6×6.
5
    for (int r = 0; r + 2 < arr.length; r++) {
6
        for (int c = 0; c + 2 < arr[r].length; c++) {
7
            int sum = arr[r][c] + arr[r][c + 1] + arr[r][c + 2]
8
                    // The single center cell of the middle row — the waist of the
9
                    // hourglass.
10
                    + arr[r + 1][c + 1]
11
                    + arr[r + 2][c] + arr[r + 2][c + 1] + arr[r + 2][c + 2];
12
            best = Math.max(best, sum);
13
        }
14
    }
15
    return best;
16
}

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

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

ComplexityO(1) time, O(1) space — 16 hourglasses × 6 additions = 96 additions regardless of input. Constant time, constant space.

E · Edge cases and pitfalls5n×n grid with n > 6 — The length-based bounds (rows−2, cols−2) handle any n ≥ 3 with no code change.Explore edge cases

Edge cases handled

n×n grid with n > 6The length-based bounds (rows−2, cols−2) handle any n ≥ 3 with no code change.
n = 3 gridExactly one hourglass; the loops run once and return its sum.

Pitfalls

Hardcoding 4 as the loop bound, then breaking when asked to generalize to n×n.
Forgetting the negative initialization — the most common wrong-answer cause.
Including the middle-side cells, turning the hourglass into a full block 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.

Zero-initialized maximum

On a grid where every hourglass sum is negative, starting at 0 returns 0 — a value that no hourglass actually produces.

Explore the code comparison

Don't write this

int best = 0;
// ... best = Math.max(best, sum);

Write this instead

int best = Integer.MIN_VALUE;
// ... best = Math.max(best, sum);

Out-of-bounds corner range

Running the corner over 0..5 makes arr[r+2] reach index 7 — an ArrayIndexOutOfBoundsException.

Explore the code comparison

Don't write this

for (int r = 0; r <= 5; r++) {
    for (int c = 0; c <= 5; c++) {
        int sum = arr[r + 2][c + 2] + /* ... */;
    }
}

Write this instead

for (int r = 0; r + 2 < arr.length; r++) {
    for (int c = 0; c + 2 < arr[r].length; c++) {
        int sum = arr[r + 2][c + 2] + /* ... */;
    }
}

Summing the full block

Adding arr[r+1][c] and arr[r+1][c+2] turns the hourglass into a 9-cell square and overcounts.

Explore the code comparison

Don't write this

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

Write this instead

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Fixed-size mask slid over a bounded grid

Code pattern to memorize

for r in 0..3:
    for c in 0..3:
        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]
        best = max(best, top + mid + bottom)

Rules to remember

1There are exactly 16 hourglasses in a 6×6 grid: 4 valid top rows × 4 valid left columns.
2Initialize best to a very negative value, not 0 — sums can be negative when all 7 cells are negative.
3The hourglass is not a full 3×3 block. The two middle-side cells g[r+1][c] and g[r+1][c+2] are excluded.
4Iterate the top-left corner only over rows 0..3 and columns 0..3 so r+2 and c+2 stay in bounds.
5Sum the 7 cells directly — there's no benefit to a prefix-sum here because the mask is tiny and fixed.

Use this pattern when

A fixed-shape stencil (hourglass, plus, cross) slides over a bounded grid
The grid dimensions are constant, so total work is a constant number of fixed-cost sums
You need the max/min of a small fixed pattern over every legal position

Choose another pattern when

The window is a variable-size rectangle whose sum changes incrementally → 2D prefix sums
You need every subrectangle sum, not one fixed shape → integral image
The grid is huge and the mask is large → precompute partial sums instead of re-summing

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

←

Rabin–Karp Substring Search (Rolling Hash)

Continue · Next problem

Array Manipulation