02 Jun 2024•TypeScript•Medium

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 < class="syntax-number">3) {
    return class="syntax-number">0;
  }
  const cols = grid[class="syntax-number">0].length;
  if (cols < class="syntax-number">3) {
    return class="syntax-number">0;
  }

  let best = Number.NEGATIVE_INFINITY;

  for (let r = class="syntax-number">0; r <= rows - class="syntax-number">3; ++r) {
    for (let c = class="syntax-number">0; c <= cols - class="syntax-number">3; ++c) {
      const sum =
        grid[r][c] +
        grid[r][c + class="syntax-number">1] +
        grid[r][c + class="syntax-number">2] +
        grid[r + class="syntax-number">1][c + class="syntax-number">1] +
        grid[r + class="syntax-number">2][c] +
        grid[r + class="syntax-number">2][c + class="syntax-number">1] +
        grid[r + class="syntax-number">2][c + class="syntax-number">2];

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

  return best;
}

export { maxSum };