FastPrepMaximum Rhombic Area Sum

Maximum Rhombic Area Sum

Hudson River Trading logoHudson River Trading● MediumINTERNOA

Problem statement

You are given a rectangular integer matrix matrix and a positive integer r.

A rhombic area of size r centered at (centerRow, centerCol) contains every cell (row, col) whose Manhattan distance from the center is less than r:

|row - centerRow| + |col - centerCol| < r

Equivalently, the center has radius number 1, its orthogonally adjacent cells have radius number 2, and all cells with radius numbers from 1 through r belong to the area.

A center is valid only when its entire rhombic area lies inside the matrix. Return the maximum sum of the matrix values in any valid rhombic area of size r.

Function

maximumRhombicSum(matrix: int[][], r: int) → int

Examples

Example 1

matrix = [[1,2,3],[4,5,6],[7,8,9]]r = 2return = 25

The only valid center is the middle cell. Its rhombic area contains 5, 2, 4, 6, and 8, whose sum is 25.

Example 2

matrix = [[-5,2],[3,1]]r = 1return = 3

With r = 1, each rhombic area contains only its center. The largest cell value is 3.

Example 3

matrix = [[1,1,1,1],[1,5,1,1],[1,1,4,1],[1,1,1,1]]r = 2return = 12

A rhombus centered at (1, 2) contains values 1, 1, 5, 1, and 4, for a sum of 12. The center (2, 1) also gives 12, and no valid center gives a larger sum.

Constraints

  • 1 ≤ matrix.length ≤ 100
  • 1 ≤ matrix[i].length ≤ 100
  • Every row has the same length.
  • -10^4 ≤ matrix[i][j] ≤ 10^4
  • 1 ≤ r ≤ min((matrix.length + 1) / 2, (matrix[0].length + 1) / 2)

More Hudson River Trading problems

See Hudson River Trading hiring insights
Saved
public int maximumRhombicSum(int[][] matrix, int r) {
    // Write your code here.
}
matrix[[1,2,3],[4,5,6],[7,8,9]]
r2
expected25
Checking account…