02 Jun 2024•Medium•TypeScript

Maximum Sum of an Hourglass

Sliding a fixed hourglass mask through the grid and tracking the best sum with constant-time updates.

Hourglasses fit inside the grid only when every interior cell touches the mask. That means we just iterate all top-left anchors except the last two rows and columns and evaluate the sum of the fixed seven cells that make the hourglass.

The trick is to keep a running sum for each candidate instead of recomputing from scratch. I subtract the leftmost column of the previous hourglass, add the rightmost column, and adjust the lone middle cell per step.

Complexity

There are (m - 2) × (n - 2) possible hourglass anchors. Each update is O(1), so the whole sweep stays O(mn) time and O(1) space.

Pitfalls

Watch the boundary indices carefully—hourglasses fail when the grid is smaller than 3×3.
Reset the rolling sum only when shifting to a new row; horizontal moves can reuse most of the work.

Solution files

TypeScript•maximum-sum-of-an-hourglass/solution.ts

function maxSum(grid: number[][]): number {
  const rows = grid.length;
  if (rows < 3) {
    return 0;
  }
  const cols = grid[0].length;
  if (cols < 3) {
    return 0;
  }

  let best = Number.NEGATIVE_INFINITY;

  for (let r = 0; r <= rows - 3; ++r) {
    for (let c = 0; c <= cols - 3; ++c) {
      const sum =
        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];

      if (sum > best) {
        best = sum;
      }
    }
  }

  return best;
}

export { maxSum };