Best Hourglass in a Grid

Medium

You get a grid grid of non-negative integers with m rows and n columns. An hourglass is a seven-cell shape inside a 3×3 square: the whole top row of the square, its center cell and the whole bottom row. The two side cells of the middle row are not part of it.


X X X
  X
X X X

The hourglass cannot be rotated and must fit entirely inside the grid. Return the largest sum a single hourglass can cover.

Example 1

grid=[[2, 0, 5, 1], [7, 3, 9, 4], [1, 6, 8, 0]] → 29

The hourglass centered on 9 gives 0 + 5 + 1 + 9 + 6 + 8 + 0 = 29. Centered on 3 it is only 2 + 0 + 5 + 3 + 1 + 6 + 8 = 25.

Example 2

grid=[[1, 1, 1], [9, 0, 9], [1, 1, 1]] → 6

There is only one hourglass. The 9s beside the center are not part of it: 3 + 0 + 3 = 6.

Constraints

3 ≤ m, n ≤ 150
All rows of grid have the same length n
0 ≤ grid[i][j] ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Matrix Prefix Sum

Similar problems

Largest Light Square Medium Neighbourhood Sums in a Grid Medium K-th Largest Corner XOR Medium Three Heaviest Diamonds Medium Balanced Square in a Grid Medium

Input

grid=[[2, 0, 5, 1], [7, 3, 9, 4], [1, 6, 8, 0]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 65 tests on the server, hidden ones included.