Maximum Sum of an Hourglass

▶

Steps

setup

Initialize variables and start first row

Set matrix dimensions and initialize max_sum to negative infinity. Prepare to process the first row where hourglass can fit (i=0).

💡 Initialization sets the stage for scanning the matrix and ensures max_sum can be updated correctly.

Line:

n = len(matrix)
m = len(matrix[0])
max_sum = float('-inf')
for i in range(n - 2):

💡 We only consider rows where a full hourglass can fit, i.e., up to n-3.

fill_row

Compute initial hourglass sum at (0,0)

Calculate the sum of the hourglass starting at row 0, column 0 by adding the top row, middle element, and bottom row elements of the hourglass.

💡 Computing the first hourglass sum in a row sets the baseline for sliding sums horizontally.

Line:

current_sum = (matrix[i][0] + matrix[i][1] + matrix[i][2] +
               matrix[i+1][1] +
               matrix[i+2][0] + matrix[i+2][1] + matrix[i+2][2])

💡 This sum includes 7 elements forming the hourglass shape starting at (0,0).

fill_row

Include middle and bottom row elements for hourglass at (0,0)

Add the middle element from row 1, column 1 and the three elements from row 2, columns 0 to 2 to complete the hourglass sum.

💡 Completing the hourglass sum requires adding the middle and bottom parts after the top row.

Line:

current_sum = (matrix[i][0] + matrix[i][1] + matrix[i][2] +
               matrix[i+1][1] +
               matrix[i+2][0] + matrix[i+2][1] + matrix[i+2][2])

💡 The hourglass sum is the sum of these 7 specific elements.

compare

Update max_sum after first hourglass sum

Compare the current_sum (13) with max_sum (-∞) and update max_sum to 13 since current_sum is greater.

💡 Tracking the maximum sum found so far is essential to return the correct answer.

Line:

if current_sum > max_sum:
    max_sum = current_sum

💡 max_sum now holds the highest hourglass sum found after processing the first hourglass.

shrink

Slide hourglass right to position (0,1): remove left column elements

Slide the hourglass one column to the right by subtracting the leftmost elements of the previous hourglass from current_sum.

💡 Removing elements that are no longer in the hourglass avoids recomputing the sum from scratch.

Line:

current_sum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1])

💡 We remove the top-left, middle-left, and bottom-left elements of the previous hourglass.

expand

Slide hourglass right to position (0,1): add right column elements

Add the new rightmost elements of the hourglass at position (0,1) to current_sum to complete the sliding update.

💡 Adding new elements entering the hourglass keeps the sum accurate without full recomputation.

Line:

current_sum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2])

💡 We add the top-right, middle-right, and bottom-right elements of the new hourglass.

compare

Compare updated hourglass sum at (0,1) with max_sum

Check if the new current_sum (10) is greater than max_sum (13). Since it is not, max_sum remains unchanged.

💡 Comparisons after each slide ensure max_sum always holds the highest sum found.

Line:

if current_sum > max_sum:
    max_sum = current_sum

💡 Not every hourglass sum will update max_sum; only larger sums do.

fill_row

Move to next row (i=1), compute initial hourglass sum at (1,0)

Increment row pointer to 1 and compute the hourglass sum starting at (1,0) by summing the top, middle, and bottom parts of the hourglass.

💡 Moving down a row resets the horizontal sliding and requires a fresh initial sum.

Line:

for i in range(n - 2):
    current_sum = (matrix[i][0] + matrix[i][1] + matrix[i][2] +
                   matrix[i+1][1] +
                   matrix[i+2][0] + matrix[i+2][1] + matrix[i+2][2])

💡 The hourglass at (1,0) includes mostly zeros, so sum will be low.

compare

Compare hourglass sum at (1,0) with max_sum

Compare the current_sum (7) with max_sum (13). Since 7 is less, max_sum remains 13.

💡 Comparisons after each initial sum ensure max_sum is always the highest found.

Line:

if current_sum > max_sum:
    max_sum = current_sum

💡 Hourglass sums can be smaller and do not always update max_sum.

shrink

Slide hourglass right to position (1,1): update sum by removing left and adding right elements

Slide hourglass right by subtracting left column elements and adding right column elements to current_sum.

💡 Sliding the hourglass horizontally updates the sum efficiently.

Line:

current_sum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1])
current_sum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2])

💡 This step shows how the sliding window technique avoids full recomputation.

compare

Compare hourglass sum at (1,1) with max_sum

Compare the updated current_sum (7) with max_sum (13). max_sum remains 13 as current_sum is smaller.

💡 Each slide requires a comparison to update max_sum if needed.

Line:

if current_sum > max_sum:
    max_sum = current_sum

💡 The algorithm correctly ignores smaller sums after sliding.

fill_row

Move to next row (i=2), compute initial hourglass sum at (2,0)

Increment row pointer to 2 and compute the hourglass sum starting at (2,0). This hourglass includes larger values, so sum may be higher.

💡 Each new row requires a fresh initial sum before sliding horizontally.

Line:

for i in range(n - 2):
    current_sum = (matrix[i][0] + matrix[i][1] + matrix[i][2] +
                   matrix[i+1][1] +
                   matrix[i+2][0] + matrix[i+2][1] + matrix[i+2][2])

💡 This hourglass sum will be computed fully from scratch.

compare

Compare hourglass sum at (2,0) with max_sum

Compare the current_sum (13) with max_sum (13). They are equal, so max_sum remains 13.

💡 Equal sums do not update max_sum but confirm the maximum found so far.

Line:

if current_sum > max_sum:
    max_sum = current_sum

💡 The algorithm correctly handles ties in maximum sums.

shrink

Slide hourglass right to position (2,1): update sum by removing left and adding right elements

Slide hourglass right by subtracting left column elements and adding right column elements to current_sum.

💡 Sliding horizontally updates the sum efficiently without full recomputation.

Line:

current_sum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1])
current_sum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2])

💡 This step demonstrates the sliding window update for the last hourglass in the row.

compare

Compare hourglass sum at (2,1) with max_sum

Compare the updated current_sum (10) with max_sum (13). max_sum remains 13 as current_sum is smaller.

💡 Each slide requires a comparison to update max_sum if needed.

Line:

if current_sum > max_sum:
    max_sum = current_sum

💡 The algorithm correctly ignores smaller sums after sliding.

reconstruct

Finish scanning all rows and columns, return max_sum

All valid hourglass positions have been processed. The maximum hourglass sum found is 13, which is returned as the final answer.

💡 Returning max_sum completes the algorithm and provides the solution.

Line:

return max_sum

💡 The algorithm efficiently found the maximum hourglass sum by sliding and comparing sums.

def max_hourglass_sum_sliding(matrix):
    n = len(matrix)  # STEP 1
    m = len(matrix[0])  # STEP 1
    max_sum = float('-inf')  # STEP 1

    for i in range(n - 2):  # STEP 1
        # Compute initial hourglass sum for first position in row i  # STEP 2-3
        current_sum = (matrix[i][0] + matrix[i][1] + matrix[i][2] +
                       matrix[i+1][1] +
                       matrix[i+2][0] + matrix[i+2][1] + matrix[i+2][2])  # STEP 2-3
        if current_sum > max_sum:  # STEP 4
            max_sum = current_sum  # STEP 4

        for j in range(1, m - 2):  # STEP 5-15
            # Slide hourglass right by updating sum  # STEP 5-6
            current_sum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1])  # STEP 5
            current_sum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2])  # STEP 6
            if current_sum > max_sum:  # STEP 7, 9, 11, 13, 15
                max_sum = current_sum  # STEP 7, 9, 11, 13, 15
    return max_sum  # STEP 16

# Example usage:
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]
]
print(max_hourglass_sum_sliding(matrix))  # Output: 13

📊

Maximum Sum of an Hourglass - Watch the Algorithm Execute, Step by Step

Watching each sum calculation and pointer movement helps you understand how the sliding window technique optimizes the search for the maximum hourglass sum without recomputing sums from scratch.

setup

i

0

1

2

3

4

Result: "-∞"

fill_row

j

0

1

2

3

4

Result: "-∞"

fill_row

j

0

1

2

3

4

Result: "-∞"

compare

j

0

1

2

3

4

Result: 13

shrink

i

0

j

1

2

3

4

Result: 13

expand

i

0

j

1

2

3

4

Result: 13

compare

i

0

j

1

2

3

4

Result: 13

fill_row

j

0

i

1

2

3

4

Result: 13

compare

j

0

i

1

2

3

4

Result: 13

shrink

0

j

1

2

3

4

Result: 13

compare

0

j

1

2

3

4

Result: 13

fill_row

j

0

1

i

2

3

4

Result: 13

compare

j

0

1

i

2

3

4

Result: 13

shrink

0

j

1

i

2

3

4

Result: 13

compare

0

j

1

i

2

3

4

Result: 13

Key Takeaways

✓ Sliding window technique efficiently updates hourglass sums by adding and removing only the changed elements.

This insight is hard to see from code alone because the sum update lines are compact; visualization shows exactly which elements are removed and added.

✓ The algorithm only computes full sums once per row and then slides horizontally, saving computation time.

Watching the initial sum calculation separate from sliding clarifies the dependency and order of operations.

✓ max_sum updates only when a strictly larger sum is found, ensuring the maximum is tracked correctly.

Seeing the comparisons step-by-step helps understand why some sums do not update max_sum.

Practice

1. Consider the following Python function that computes the sum of the diagonals of a square matrix:

def diagonalSum(mat):
    total = 0
    n = len(mat)
    for i in range(n):
        total += mat[i][i] + mat[i][n - 1 - i]
    if n % 2 == 1:
        total -= mat[n//2][n//2]
    return total

matrix = [[1,2,3],[4,5,6],[7,8,9]]
print(diagonalSum(matrix))

What is the value of total after the loop completes but before the if-condition is applied?

easy

A. 15

B. 25

C. 30

D. 45

Solution

1. Step 1: Trace the loop iterations

   For i=0: total = 0 + mat[0][0] + mat[0][2] = 0 + 1 + 3 = 4 For i=1: total = 4 + mat[1][1] + mat[1][1] = 4 + 5 + 5 = 14 For i=2: total = 14 + mat[2][2] + mat[2][0] = 14 + 9 + 7 = 30

2. Step 2: Note that the if-condition has not yet been applied

   The total before subtracting the center element is 30.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sum of diagonals before center correction is 30 [OK]

Hint: Sum both diagonals first, then adjust center if needed [OK]

Common Mistakes:

• Forgetting to subtract center element once
• Double counting center element
• Off-by-one in indices

2. Consider the following code that transposes a square matrix in-place:

def transpose(matrix):
    n = len(matrix)
    if n == 1:
        return
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
transpose(mat)
print(mat)

What is the value of mat[1][2] after the function call?

easy

A. 8

B. 6

C. 4

D. 5

Solution

1. Step 1: Trace swaps affecting mat[1][2]

   Initially, mat[1][2] = 6. The swap occurs when i=1, j=2 swapping mat[1][2] and mat[2][1]. mat[2][1] is 8.

2. Step 2: After swap, mat[1][2] becomes 8

   Thus, mat[1][2] = 8 after transpose.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Swapping upper triangle elements swaps mat[1][2] with mat[2][1] correctly [OK]

Hint: Trace swaps only in upper triangle [OK]

Common Mistakes:

• Confusing indices i and j during swap
• Off-by-one errors in loops
• Assuming mat[1][2] remains unchanged

3. What is the time complexity of the optimal in-place Game of Life solution that encodes states using 4 integer values, given an m x n board?

medium

A. O(m + n) since only rows and columns are scanned

B. O(m * n * 8 * 2) due to checking neighbors twice

C. O(m * n * m * n) because each cell checks all other cells as neighbors

D. O(m * n) because each cell and its neighbors are processed in constant time

Solution

1. Step 1: Identify loops and operations

   Outer loops iterate over all m*n cells. For each cell, 8 neighbors are checked in constant time.

2. Step 2: Calculate total operations

   Total operations = m*n*8 = O(m*n), since 8 is constant.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Neighbor checks are constant per cell -> linear in board size [OK]

Hint: Neighbor checks are constant per cell, so linear overall [OK]

Common Mistakes:

• Mistaking neighbor checks as nested loops over entire board
• Counting neighbor checks twice incorrectly
• Confusing linear scan with quadratic complexity

4. Identify the bug in the following in-place Game of Life code snippet that causes incorrect neighbor counts and final states.

medium

A. Line checking neighbors lacks boundary condition checks causing index errors

B. Final loop does not convert encoded states back to original states

C. Neighbor counting incorrectly includes dead cells as live

D. Encoding uses wrong integers for state transitions

Solution

1. Step 1: Examine neighbor counting loop

   The code checks board[x][y] without verifying if x,y are within valid indices, risking index errors or invalid counts.

2. Step 2: Confirm other parts are correct

   Final decoding loop correctly converts 2->0 and 3->1; encoding uses correct integers; neighbor counting excludes dead cells properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing boundary check causes incorrect neighbor counts or runtime errors [OK]

Hint: Always check boundaries before accessing neighbors [OK]

Common Mistakes:

• Forgetting boundary checks in neighbor loops
• Not finalizing encoded states after first pass
• Misusing encoding integers

5. Suppose you need to transpose a non-square matrix (m x n) in-place, but the matrix is stored as a flat array in row-major order. Which approach correctly handles this scenario?

hard

A. Transpose in-place by swapping elements only in the upper triangle of the matrix.

B. Use the same in-place swapping approach as for square matrices, swapping elements symmetrically across the diagonal.

C. Create a new matrix of size n x m and copy elements accordingly, since in-place transpose is not possible for non-square matrices.

D. Use a recursive approach to swap elements in cycles to achieve in-place transpose.

Solution

1. Step 1: Understand matrix shape constraints

   In-place transpose by swapping only works for square matrices because indices map symmetrically.

2. Step 2: For non-square matrices, in-place transpose is not possible

   Because the shape changes from m x n to n x m, a new matrix must be created to hold the transposed data.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Non-square matrix transpose requires extra space due to dimension change [OK]

Hint: In-place transpose only works for square matrices [OK]

Common Mistakes:

• Trying to swap elements in-place for non-square matrices
• Assuming upper triangle swaps apply to rectangular matrices
• Ignoring dimension changes after transpose