FastPrepMaximum Diamond Sum

Maximum Diamond Sum

Hudson River Trading logoHudson River Trading● MediumNEW GRADOA
Learn

Problem statement

You are given an integer matrix grid and a list diamonds. Each diamond is [row, column, radius] and contains every cell whose Manhattan distance from its center is at most radius.

Only diamonds fully contained in the matrix are listed. Return the maximum sum of the cells in any listed diamond.

Function

maximumDiamondSum(grid: int[][], diamonds: int[][]) → long

Examples

Example 1

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

The radius-one diamond contains 2, 4, 5, 6, and 8, whose sum is 25.

Example 2

grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1]]diamonds = [[2,2,2],[1,1,1]]return = 13

The radius-two diamond has thirteen cells, more than the five-cell alternative.

Example 3

grid = [[-5,-1,-5],[-1,10,-1],[-5,-1,-5]]diamonds = [[1,1,1],[1,1,0]]return = 10

The center-only diamond is better because the surrounding values reduce the larger diamond's sum.

Constraints

  • 1 <= grid.length, grid[0].length <= 200.
  • The matrix is rectangular and -10^6 <= grid[r][c] <= 10^6.
  • 1 <= diamonds.length <= 10000.
  • Every diamond has nonnegative radius and is fully contained in the matrix.
  • The total number of cells across all listed diamonds is at most 10^6.

More Hudson River Trading problems

See Hudson River Trading hiring insights
public long maximumDiamondSum(int[][] grid, int[][] diamonds) {
    // Write your code here.
}
grid[[1,2,3],[4,5,6],[7,8,9]]
diamonds[[1,1,1],[1,1,0]]
expected25
Checking account…