Maximum Sum of an Hourglass

MediumArrayMatrixPrefix Sum

Solution

export function maxSum(grid: number[][]): number {
  const [m, n] = [grid.length, grid[0].length];
 
  let answer = 0;
  for (let y = 0; y < m - 2; y++) {
    for (let x = 0; x < n - 2; x++) {
      answer = Math.max(answer, sumHourglass(grid, y, x));
    }
  }
  return answer;
}
 
function sumHourglass(grid: number[][], y: number, x: number) {
  let result = 0;
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (i === 1 && j !== 1) continue;
      result += grid[y + i][x + j];
    }
  }
  return result;
}

Complexity

  • Time: O(M * N)
  • Space: O(1)