Maximum Sum of an Hourglass

🎯

Maximum Sum of an Hourglass

mediumMATRIXAmazonGoogle

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

💡 This problem involves scanning a 2D matrix to find a fixed pattern sum (hourglass shape). Beginners often struggle because they need to carefully handle indices and understand how to iterate over submatrices without going out of bounds.

📋

Problem Statement

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

💡

Example

Input"[[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]]"

Output13

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

• Matrix with all negative numbers → maximum sum is the least negative hourglass
• Matrix with minimum size 3x3 → only one hourglass possible
• Matrix with large positive and negative values → test integer overflow handling
• Matrix where multiple hourglasses have the same maximum sum → ensure correct max is returned

⚠️

Common Mistakes

Incorrect hourglass indexing causing out-of-bounds errors

Runtime error or incorrect sums

✅ Ensure loops run only until n-2 and m-2 and carefully index hourglass elements

Summing all 3x3 elements instead of hourglass pattern

Wrong sums and incorrect maximum

✅ Sum only the hourglass elements explicitly, skipping the two corners of the middle row

Not updating max_sum correctly when all values are negative

Returns 0 or wrong max instead of correct negative max

✅ Initialize max_sum to -infinity or minimum integer value

Recomputing sums fully inside nested loops without optimization

Slower code, may time out on large inputs

✅ Use prefix sums or sliding window to reduce repeated additions

Forgetting to handle matrices smaller than 3x3

Index errors or invalid results

✅ Check input size and handle or reject invalid inputs

🧠

Brute Force (Nested Loops Over All Hourglasses)

💡 Starting with brute force helps understand the problem deeply by explicitly checking every possible hourglass, even though it's not efficient for large inputs.

Intuition

Check every possible hourglass by iterating over all valid top-left positions and summing the fixed hourglass pattern explicitly.

Algorithm

1. Iterate over all valid top-left positions where an hourglass can fit (i from 0 to n-3, j from 0 to m-3).
2. For each position, sum the values of the hourglass shape explicitly.
3. Keep track of the maximum sum found so far.
4. Return the maximum sum after checking all hourglasses.

💡 The main challenge is correctly indexing the hourglass elements and ensuring you don't go out of matrix bounds.

</>

Code

def max_hourglass_sum(matrix):
    n = len(matrix)
    m = len(matrix[0])
    max_sum = float('-inf')
    for i in range(n - 2):
        for j in range(m - 2):
            current_sum = (matrix[i][j] + matrix[i][j+1] + matrix[i][j+2] +
                           matrix[i+1][j+1] +
                           matrix[i+2][j] + matrix[i+2][j+1] + matrix[i+2][j+2])
            if current_sum > max_sum:
                max_sum = current_sum
    return max_sum

# 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(matrix))  # Output: 13

Line Notes

n = len(matrix)Determine number of rows to set iteration limits

m = len(matrix[0])Determine number of columns to set iteration limits

for i in range(n - 2)Iterate only where hourglass top row fits

for j in range(m - 2)Iterate only where hourglass left column fits

current_sum = (matrix[i][j] + matrix[i][j+1] + matrix[i][j+2] +Sum top row of hourglass explicitly

matrix[i+1][j+1] +Add middle element of hourglass

matrix[i+2][j] + matrix[i+2][j+1] + matrix[i+2][j+2])Sum bottom row of hourglass explicitly

if current_sum > max_sum:Update max_sum if current hourglass sum is greater

public class Solution {
    public static int maxHourglassSum(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i <= n - 3; i++) {
            for (int j = 0; j <= m - 3; j++) {
                int currentSum = matrix[i][j] + matrix[i][j+1] + matrix[i][j+2]
                               + matrix[i+1][j+1]
                               + matrix[i+2][j] + matrix[i+2][j+1] + matrix[i+2][j+2];
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[][] 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}
        };
        System.out.println(maxHourglassSum(matrix)); // Output: 13
    }
}

Line Notes

int n = matrix.length;Get number of rows for iteration bounds

int m = matrix[0].length;Get number of columns for iteration bounds

for (int i = 0; i <= n - 3; i++) {Loop over valid hourglass top rows

for (int j = 0; j <= m - 3; j++) {Loop over valid hourglass left columns

int currentSum = matrix[i][j] + matrix[i][j+1] + matrix[i][j+2]Sum top row of hourglass explicitly

+ matrix[i+1][j+1]Add middle element of hourglass

+ matrix[i+2][j] + matrix[i+2][j+1] + matrix[i+2][j+2];Sum bottom row of hourglass explicitly

if (currentSum > maxSum) {Update maxSum if currentSum is greater

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int maxHourglassSum(const vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    int maxSum = INT_MIN;
    for (int i = 0; i <= n - 3; i++) {
        for (int j = 0; j <= m - 3; j++) {
            int currentSum = matrix[i][j] + matrix[i][j+1] + matrix[i][j+2]
                           + matrix[i+1][j+1]
                           + matrix[i+2][j] + matrix[i+2][j+1] + matrix[i+2][j+2];
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
    }
    return maxSum;
}

int main() {
    vector<vector<int>> 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}
    };
    cout << maxHourglassSum(matrix) << endl; // Output: 13
    return 0;
}

Line Notes

int n = matrix.size();Get number of rows for iteration limits

int m = matrix[0].size();Get number of columns for iteration limits

for (int i = 0; i <= n - 3; i++) {Loop over valid hourglass top rows

for (int j = 0; j <= m - 3; j++) {Loop over valid hourglass left columns

int currentSum = matrix[i][j] + matrix[i][j+1] + matrix[i][j+2]Sum top row of hourglass explicitly

+ matrix[i+1][j+1]Add middle element of hourglass

+ matrix[i+2][j] + matrix[i+2][j+1] + matrix[i+2][j+2];Sum bottom row of hourglass explicitly

if (currentSum > maxSum) {Update maxSum if currentSum is greater

function maxHourglassSum(matrix) {
    const n = matrix.length;
    const m = matrix[0].length;
    let maxSum = Number.NEGATIVE_INFINITY;
    for (let i = 0; i <= n - 3; i++) {
        for (let j = 0; j <= m - 3; j++) {
            const currentSum = matrix[i][j] + matrix[i][j+1] + matrix[i][j+2]
                             + matrix[i+1][j+1]
                             + matrix[i+2][j] + matrix[i+2][j+1] + matrix[i+2][j+2];
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
    }
    return maxSum;
}

// Example usage:
const 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]
];
console.log(maxHourglassSum(matrix)); // Output: 13

Line Notes

const n = matrix.length;Get number of rows for iteration bounds

const m = matrix[0].length;Get number of columns for iteration bounds

for (let i = 0; i <= n - 3; i++) {Loop over valid hourglass top rows

for (let j = 0; j <= m - 3; j++) {Loop over valid hourglass left columns

const currentSum = matrix[i][j] + matrix[i][j+1] + matrix[i][j+2]Sum top row of hourglass explicitly

+ matrix[i+1][j+1]Add middle element of hourglass

+ matrix[i+2][j] + matrix[i+2][j+1] + matrix[i+2][j+2];Sum bottom row of hourglass explicitly

if (currentSum > maxSum) {Update maxSum if currentSum is greater

⏱

Complexity

TimeO(n*m)

SpaceO(1)

We iterate over each valid hourglass top-left position once, and sum a fixed 7 elements each time, so total operations proportional to number of hourglasses ~ (n-2)*(m-2).

💡 For a 1000x1000 matrix, this means roughly 1 million hourglasses checked, each summing 7 elements, about 7 million operations.

Interview Verdict: Accepted

Though brute force is simple and accepted for medium constraints, it may be slow for very large inputs but is a solid baseline.

🧠

Prefix Sum Optimization

💡 Using prefix sums helps reduce repeated summations by precomputing cumulative sums, speeding up sum queries for submatrices.

Intuition

Precompute prefix sums for the matrix to quickly calculate sums of rows or sub-rectangles, then use these to compute hourglass sums faster.

Algorithm

1. Compute prefix sums for each row to quickly get sums of any 3 consecutive elements in O(1).
2. Iterate over all valid hourglass top-left positions.
3. Use prefix sums to get top and bottom rows sums quickly.
4. Add the middle element explicitly and track the maximum sum.

💡 The key is to reduce repeated addition of the same elements by using prefix sums for rows.

</>

Code

def max_hourglass_sum_prefix(matrix):
    n = len(matrix)
    m = len(matrix[0])
    # Compute prefix sums for each row
    prefix = [[0]*(m+1) for _ in range(n)]
    for i in range(n):
        for j in range(m):
            prefix[i][j+1] = prefix[i][j] + matrix[i][j]

    max_sum = float('-inf')
    for i in range(n - 2):
        for j in range(m - 2):
            top = prefix[i][j+3] - prefix[i][j]
            mid = matrix[i+1][j+1]
            bot = prefix[i+2][j+3] - prefix[i+2][j]
            current_sum = top + mid + bot
            if current_sum > max_sum:
                max_sum = current_sum
    return max_sum

# 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_prefix(matrix))  # Output: 13

Line Notes

prefix = [[0]*(m+1) for _ in range(n)]Create prefix sum array with extra column for easier calculations

prefix[i][j+1] = prefix[i][j] + matrix[i][j]Build prefix sums row-wise to get cumulative sums

top = prefix[i][j+3] - prefix[i][j]Sum top row of hourglass using prefix sums in O(1)

mid = matrix[i+1][j+1]Middle element added explicitly as it's a single element

bot = prefix[i+2][j+3] - prefix[i+2][j]Sum bottom row of hourglass using prefix sums in O(1)

if current_sum > max_sum:Update max_sum if current hourglass sum is greater

public class Solution {
    public static int maxHourglassSumPrefix(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] prefix = new int[n][m+1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                prefix[i][j+1] = prefix[i][j] + matrix[i][j];
            }
        }
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i <= n - 3; i++) {
            for (int j = 0; j <= m - 3; j++) {
                int top = prefix[i][j+3] - prefix[i][j];
                int mid = matrix[i+1][j+1];
                int bot = prefix[i+2][j+3] - prefix[i+2][j];
                int currentSum = top + mid + bot;
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[][] 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}
        };
        System.out.println(maxHourglassSumPrefix(matrix)); // Output: 13
    }
}

Line Notes

int[][] prefix = new int[n][m+1];Create prefix sum array with extra column for easier calculations

prefix[i][j+1] = prefix[i][j] + matrix[i][j];Build prefix sums row-wise for O(1) range sums

int top = prefix[i][j+3] - prefix[i][j];Sum top row of hourglass using prefix sums

int mid = matrix[i+1][j+1];Middle element added explicitly

int bot = prefix[i+2][j+3] - prefix[i+2][j];Sum bottom row of hourglass using prefix sums

if (currentSum > maxSum) {Update maxSum if currentSum is greater

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int maxHourglassSumPrefix(const vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    vector<vector<int>> prefix(n, vector<int>(m+1, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            prefix[i][j+1] = prefix[i][j] + matrix[i][j];
        }
    }
    int maxSum = INT_MIN;
    for (int i = 0; i <= n - 3; i++) {
        for (int j = 0; j <= m - 3; j++) {
            int top = prefix[i][j+3] - prefix[i][j];
            int mid = matrix[i+1][j+1];
            int bot = prefix[i+2][j+3] - prefix[i+2][j];
            int currentSum = top + mid + bot;
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
    }
    return maxSum;
}

int main() {
    vector<vector<int>> 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}
    };
    cout << maxHourglassSumPrefix(matrix) << endl; // Output: 13
    return 0;
}

Line Notes

vector<vector<int>> prefix(n, vector<int>(m+1, 0));Create prefix sum array with extra column for easier calculations

prefix[i][j+1] = prefix[i][j] + matrix[i][j];Build prefix sums row-wise for O(1) range sums

int top = prefix[i][j+3] - prefix[i][j];Sum top row of hourglass using prefix sums

int mid = matrix[i+1][j+1];Middle element added explicitly

int bot = prefix[i+2][j+3] - prefix[i+2][j];Sum bottom row of hourglass using prefix sums

if (currentSum > maxSum) {Update maxSum if currentSum is greater

function maxHourglassSumPrefix(matrix) {
    const n = matrix.length;
    const m = matrix[0].length;
    const prefix = Array.from({length: n}, () => Array(m+1).fill(0));
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            prefix[i][j+1] = prefix[i][j] + matrix[i][j];
        }
    }
    let maxSum = Number.NEGATIVE_INFINITY;
    for (let i = 0; i <= n - 3; i++) {
        for (let j = 0; j <= m - 3; j++) {
            const top = prefix[i][j+3] - prefix[i][j];
            const mid = matrix[i+1][j+1];
            const bot = prefix[i+2][j+3] - prefix[i+2][j];
            const currentSum = top + mid + bot;
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
    }
    return maxSum;
}

// Example usage:
const 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]
];
console.log(maxHourglassSumPrefix(matrix)); // Output: 13

Line Notes

const prefix = Array.from({length: n}, () => Array(m+1).fill(0));Create prefix sum array with extra column for easier calculations

prefix[i][j+1] = prefix[i][j] + matrix[i][j];Build prefix sums row-wise for O(1) range sums

const top = prefix[i][j+3] - prefix[i][j];Sum top row of hourglass using prefix sums

const mid = matrix[i+1][j+1];Middle element added explicitly

const bot = prefix[i+2][j+3] - prefix[i+2][j];Sum bottom row of hourglass using prefix sums

if (currentSum > maxSum) {Update maxSum if currentSum is greater

⏱

Complexity

TimeO(n*m)

SpaceO(n*m)

Prefix sums take O(n*m) to compute, then each hourglass sum is computed in O(1), total O(n*m).

💡 This approach is faster for large inputs because it avoids repeated addition inside the nested loops.

Interview Verdict: Accepted

This is a practical optimization over brute force, often expected in interviews to show understanding of prefix sums.

🧠

Sliding Window with Fixed Pattern Sum

💡 This approach treats the hourglass as a fixed pattern and slides it over the matrix, computing sums incrementally to avoid recomputing entire sums each time.

Intuition

Since the hourglass shape is fixed, we can slide it across the matrix and update sums by subtracting elements that leave the window and adding new elements entering, reducing redundant calculations.

Algorithm

1. Precompute the sum of the first hourglass in each row segment.
2. For each row where hourglass can fit, slide the hourglass horizontally, updating the sum by removing leftmost elements and adding rightmost elements of the hourglass pattern.
3. Keep track of the maximum sum found.
4. Return the maximum sum after processing all positions.

💡 The challenge is carefully updating sums to reflect the hourglass shape while sliding horizontally.

</>

Code

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

    for i in range(n - 2):
        # Compute initial hourglass sum for first position in row i
        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])
        if current_sum > max_sum:
            max_sum = current_sum

        for j in range(1, m - 2):
            # Slide hourglass right by updating sum
            # Remove left column elements and add right column elements
            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])
            if current_sum > max_sum:
                max_sum = current_sum
    return max_sum

# 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

Line Notes

for i in range(n - 2):Iterate over rows where hourglass top fits

current_sum = (matrix[i][0] + matrix[i][1] + matrix[i][2] +Compute initial hourglass sum at first column

matrix[i+1][1] +Add middle element of hourglass

matrix[i+2][0] + matrix[i+2][1] + matrix[i+2][2])Add bottom row of hourglass

for j in range(1, m - 2):Slide hourglass horizontally across columns

current_sum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1])Remove elements leaving hourglass on left

current_sum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2])Add new elements entering hourglass on right

if current_sum > max_sum:Update max_sum if current_sum is greater

public class Solution {
    public static int maxHourglassSumSliding(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i <= n - 3; i++) {
            int currentSum = 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];
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
            for (int j = 1; j <= m - 3; j++) {
                currentSum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1]);
                currentSum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2]);
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[][] 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}
        };
        System.out.println(maxHourglassSumSliding(matrix)); // Output: 13
    }
}

Line Notes

for (int i = 0; i <= n - 3; i++) {Iterate over rows where hourglass top fits

int currentSum = matrix[i][0] + matrix[i][1] + matrix[i][2]Compute initial hourglass sum at first column

+ matrix[i+1][1]Add middle element of hourglass

+ matrix[i+2][0] + matrix[i+2][1] + matrix[i+2][2];Add bottom row of hourglass

for (int j = 1; j <= m - 3; j++) {Slide hourglass horizontally across columns

currentSum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1]);Remove elements leaving hourglass on left

currentSum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2]);Add new elements entering hourglass on right

if (currentSum > maxSum) {Update maxSum if currentSum is greater

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int maxHourglassSumSliding(const vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    int maxSum = INT_MIN;

    for (int i = 0; i <= n - 3; i++) {
        int currentSum = 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];
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
        for (int j = 1; j <= m - 3; j++) {
            currentSum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1]);
            currentSum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2]);
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
    }
    return maxSum;
}

int main() {
    vector<vector<int>> 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}
    };
    cout << maxHourglassSumSliding(matrix) << endl; // Output: 13
    return 0;
}

Line Notes

for (int i = 0; i <= n - 3; i++) {Iterate over rows where hourglass top fits

int currentSum = matrix[i][0] + matrix[i][1] + matrix[i][2]Compute initial hourglass sum at first column

+ matrix[i+1][1]Add middle element of hourglass

+ matrix[i+2][0] + matrix[i+2][1] + matrix[i+2][2];Add bottom row of hourglass

for (int j = 1; j <= m - 3; j++) {Slide hourglass horizontally across columns

currentSum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1]);Remove elements leaving hourglass on left

currentSum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2]);Add new elements entering hourglass on right

if (currentSum > maxSum) {Update maxSum if currentSum is greater

function maxHourglassSumSliding(matrix) {
    const n = matrix.length;
    const m = matrix[0].length;
    let maxSum = Number.NEGATIVE_INFINITY;

    for (let i = 0; i <= n - 3; i++) {
        let currentSum = 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];
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
        for (let j = 1; j <= m - 3; j++) {
            currentSum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1]);
            currentSum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2]);
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
    }
    return maxSum;
}

// Example usage:
const 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]
];
console.log(maxHourglassSumSliding(matrix)); // Output: 13

Line Notes

for (let i = 0; i <= n - 3; i++) {Iterate over rows where hourglass top fits

let currentSum = matrix[i][0] + matrix[i][1] + matrix[i][2]Compute initial hourglass sum at first column

+ matrix[i+1][1]Add middle element of hourglass

+ matrix[i+2][0] + matrix[i+2][1] + matrix[i+2][2];Add bottom row of hourglass

for (let j = 1; j <= m - 3; j++) {Slide hourglass horizontally across columns

currentSum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1]);Remove elements leaving hourglass on left

currentSum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2]);Add new elements entering hourglass on right

if (currentSum > maxSum) {Update maxSum if currentSum is greater

⏱

Complexity

TimeO(n*m)

SpaceO(1)

We compute the first hourglass sum per row and then slide horizontally updating sums in O(1) per step, so total O(n*m).

💡 This approach is efficient and uses constant extra space, making it ideal for large matrices.

Interview Verdict: Accepted

This is the most optimal approach for this problem, demonstrating mastery of sliding window techniques on fixed patterns.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the sliding window approach (Approach 3) is ideal for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*m)	O(1)	No	N/A	Mention to show understanding; code only if input size is small
2. Prefix Sum Optimization	O(n*m)	O(n*m)	No	N/A	Good to mention as optimization; code if comfortable with prefix sums
3. Sliding Window with Fixed Pattern Sum	O(n*m)	O(1)	No	N/A	Best approach to code in interview for efficiency and clarity

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly during interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach and its time complexity.Step 3: Suggest prefix sums to optimize repeated summations.Step 4: Explain sliding window optimization for further speedup.Step 5: Code the chosen approach carefully, test with examples and edge cases.

Time Allocation

Clarify: 2min → Approach discussion: 5min → Coding: 10min → Testing & edge cases: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your ability to handle matrix indexing, optimize nested loops, and apply prefix sums or sliding window techniques.

Common Follow-ups

• What if the hourglass shape changes? → Adapt the pattern and indexing accordingly.
• How to handle very large matrices efficiently? → Use sliding window and constant space optimizations.

💡 These follow-ups test your flexibility and understanding of pattern-based matrix problems.

🔍

Pattern Recognition

When to Use

1) Fixed shape sum in matrix, 2) Need max/min sum of sub-pattern, 3) Sliding window or prefix sums applicable, 4) Matrix boundaries must be handled carefully

Signature Phrases

maximum sum of hourglassfixed 3x3 patternsliding window over matrix

NOT This Pattern When

Problems involving variable-sized submatrices or dynamic programming over matrix paths

Similar Problems

Maximum Submatrix Sum - similar concept but for rectangular submatricesSliding Window Maximum in 2D - uses sliding window technique in matrices

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. Consider this buggy code snippet for diagonal traversal. Which line contains the subtle bug that causes incorrect traversal or index errors?

def findDiagonalOrder(mat):
    if not mat or not mat[0]:
        return []
    m, n = len(mat), len(mat[0])
    result = []
    for d in range(m + n - 1):
        r_start = max(0, d - n + 1)
        r_end = min(d, m - 1)
        if d % 2 == 0:
            for r in range(r_start, r_end + 1):  # Bug here: direction wrong
                c = d - r
                result.append(mat[r][c])
        else:
            for r in range(r_end, r_start - 1, -1):
                c = d - r
                result.append(mat[r][c])
    return result

medium

A. Line with 'r_start = max(0, d - n + 1)'

B. Line with 'for r in range(r_start, r_end + 1):' inside even diagonal block

C. Line with 'c = d - r' inside loops

D. Line with 'for d in range(m + n - 1):'

Solution

1. Step 1: Identify traversal direction for even diagonals

   Even diagonals must traverse from r_end down to r_start (descending).

2. Step 2: Check loop direction in buggy code

   The loop uses ascending range from r_start to r_end, which is incorrect and causes wrong order or index errors.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Fixing loop direction restores correct traversal [OK]

Hint: Even diagonals traverse downward (descending indices) [OK]

Common Mistakes:

• Using ascending loop for even diagonals causing order errors

3. 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

4. The following code attempts to compute the sum of the diagonals of a square matrix. Identify the line that contains a subtle bug causing incorrect results for odd-sized matrices.

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]  # Bug here
    return total

medium

A. Line 5: total += mat[i][i] + mat[i][n - 1 - i]

B. Line 8: total += mat[n//2][n//2] # Bug here

C. Line 7: if n % 2 == 1:

D. Line 4: for i in range(n):

Solution

1. Step 1: Understand double counting of center element

   For odd n, the center element mat[n//2][n//2] is added twice in the loop.

2. Step 2: Identify the fix

   The code should subtract the center element once to avoid double counting, but line 8 adds it again, increasing total incorrectly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Adding center element again causes sum to be too large [OK]

Hint: Center element must be subtracted once if n is odd [OK]

Common Mistakes:

• Adding instead of subtracting center element
• Incorrect index calculation for secondary diagonal
• Ignoring odd-sized matrix special case

5. The following code attempts to return the spiral order of a matrix. Which line contains a subtle bug that can cause repeated elements or index errors?

medium

A. Line where bottom row is traversed without checking if top <= bottom

B. Line where right is decremented after traversing the right column

C. Line where left column is traversed with boundary check

D. Line where top is incremented after traversing the top row

Solution

1. Step 1: Identify missing boundary check

   The code traverses the bottom row without verifying if top <= bottom, which can cause duplicates or index errors when boundaries cross.

2. Step 2: Confirm other lines are correct

   Top increment, right decrement, and left column traversal have proper boundary checks or are logically correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing boundary check before bottom row traversal causes subtle bugs [OK]

Hint: Check boundary conditions before each traversal [OK]

Common Mistakes:

• Forgetting boundary checks before bottom or left traversal
• Incorrectly updating boundaries causing infinite loops
• Misplaced increments/decrements