Maximum Sum of a Filled Diamond That Fits Inside an Integer Grid
Company: Hudson
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given an `m x n` grid of integers. A diamond is described by a center cell `(r, c)` and a radius `k >= 0`. It contains every cell `(i, j)` whose Manhattan distance from the center is at most `k`, that is, every cell with `|i - r| + |j - c| <= k`. The sum of a diamond is the total of the values in all of those cells: the interior counts, not only the border.
A diamond is valid when every one of its cells lies inside the grid. Return the largest sum over all valid diamonds.
### Function Signature
```python
def max_diamond_sum(grid: list[list[int]]) -> int:
```
### Rules
- Rows are numbered `0` to `m - 1` from top to bottom, and columns `0` to `n - 1` from left to right.
- A diamond with center `(r, c)` and radius `k` is valid exactly when `r - k >= 0`, `c - k >= 0`, `r + k <= m - 1` and `c + k <= n - 1`.
- Radius `0` is allowed: that diamond is the single cell `(r, c)`. Every grid therefore has at least one valid diamond.
- Values may be negative.
- The answer is a single integer, the maximum sum, so it is unique.
### Constraints
- `1 <= m, n <= 100`, where `m = len(grid)` and `n = len(grid[0])`; every row has exactly `n` values.
- `-10^4 <= grid[i][j] <= 10^4`
- A valid diamond has at most 4,901 cells (radius 49), so every diamond sum lies between `-49010000` and `49010000` and fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: 25
```
The only valid diamond with radius 1 is centered at `(1, 1)` and covers the values 2, 4, 5, 6 and 8, for a sum of 25. No radius-2 diamond fits. Every other valid diamond is a single cell, and the largest cell is 9.
**Example 2**
```text
Input: grid = [[-5, -1, -5], [-1, 10, -1], [-5, -1, -5]]
Output: 10
```
The radius-1 diamond centered at `(1, 1)` sums to -1 - 1 + 10 - 1 - 1 = 6. The single-cell diamond at `(1, 1)` sums to 10, which is larger.
**Example 3**
```text
Input: grid = [[0, 1, 0, 9], [1, 1, 1, 9], [0, 1, 0, 9]]
Output: 11
```
Radius-1 diamonds fit only at centers `(1, 1)` and `(1, 2)`. The first covers 1, 1, 1, 1 and 1 for a sum of 5. The second covers 0 above, 0 below, 1 on the left, 9 on the right and 1 at the center, for a sum of 11. The largest single cell is 9, and no radius-2 diamond fits.
Overview: Online assessment coding problem: given an integer grid, find the largest sum over every filled diamond, defined by a center cell and a Manhattan-distance radius, that fits entirely inside the grid. It tests careful boundary handling and computing many overlapping region sums efficiently.
Read the full Hudson Software Engineer interview experience this question came from
You are given an `m x n` grid of integers. A diamond is described by a center cell `(r, c)` and a radius `k >= 0`. It contains every cell `(i, j)` whose Manhattan distance from the center is at most `k`, that is, every cell with `|i - r| + |j - c| <= k`. The sum of a diamond is the total of the values in all of those cells: the interior counts, not only the border.
A diamond is valid when every one of its cells lies inside the grid. Implement `max_diamond_sum(grid)`, which returns the largest sum over all valid diamonds as a single integer.
Rules:
- Rows are numbered `0` to `m - 1` from top to bottom, and columns `0` to `n - 1` from left to right.
- A diamond with center `(r, c)` and radius `k` is valid exactly when `r - k >= 0`, `c - k >= 0`, `r + k <= m - 1` and `c + k <= n - 1`.
- Radius `0` is allowed: that diamond is the single cell `(r, c)`. Every grid therefore has at least one valid diamond.
- Values may be negative.
- The answer is a single integer, the maximum sum, so it is unique.
Constraints:
- `1 <= m, n <= 100`, where `m = len(grid)` and `n = len(grid[0])`; every row has exactly `n` values.
- `-10^4 <= grid[i][j] <= 10^4`
- A valid diamond has at most 4,901 cells (radius 49), so every diamond sum lies between `-49010000` and `49010000`. No sum can exceed 2^31 - 1, so a 32-bit signed integer (`int` in Java and C++) holds every sum and the answer.
Example 1:
Input: grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: 25
The only valid radius-1 diamond is centered at (1, 1) and covers the values 2, 4, 5, 6 and 8, for a sum of 25. No radius-2 diamond fits. Every other valid diamond is a single cell, and the largest cell is 9.
Example 2:
Input: grid = [[-5, -1, -5], [-1, 10, -1], [-5, -1, -5]]
Output: 10
The radius-1 diamond centered at (1, 1) sums to -1 - 1 + 10 - 1 - 1 = 6. The single-cell diamond at (1, 1) sums to 10, which is larger.
Constraints
- 1 <= m, n <= 100, where m = len(grid) and n = len(grid[0]); every row has exactly n values.
- -10^4 <= grid[i][j] <= 10^4
- A valid diamond has at most 4,901 cells (radius 49), so every diamond sum lies between -49010000 and 49010000 and fits in a 32-bit signed integer.
Examples
Input: ([[1, 2, 3], [4, 5, 6], [7, 8, 9]],)
Expected Output: 25
Explanation: Source example 1: the only radius-1 diamond, centered at (1, 1), sums 2 + 4 + 5 + 6 + 8 = 25, which beats the largest single cell 9.
Input: ([[-5, -1, -5], [-1, 10, -1], [-5, -1, -5]],)
Expected Output: 10
Explanation: Source example 2: the radius-1 diamond at (1, 1) sums to 6, so the single cell 10 wins; the largest radius is not always best.
Hints
- A diamond centered at (r, c) stays inside the grid only up to radius min(r, c, m - 1 - r, n - 1 - c); radius 0 is always allowed.
- Because values can be negative, the largest radius at a center is not automatically the best one: every valid radius, including the single cell, is a candidate.
- The sum counts every cell within Manhattan distance k of the center, the interior as well as the border.