Difficulty: Easy | Acceptance: 76.50% | Paid: No Topics: Array, Hash Table, Design, Matrix, Simulation
You are given a n x n grid where each cell contains a unique value from 0 to n² - 1. Design a service that supports two operations:
- adjacentSum(value): Returns the sum of all adjacent cells (up, down, left, right) that contain the given value.
- diagonalSum(value): Returns the sum of all diagonal cells (top-left, top-right, bottom-left, bottom-right) that contain the given value.
If a neighbor does not exist (i.e., the cell is on the border of the grid), it is not included in the sum.
- Examples
- Constraints
- Hash Map Position Lookup
- Precomputed Sums
- Brute Force Grid Search
Examples
Example 1:
Input:
["NeighborSum", "adjacentSum", "adjacentSum", "diagonalSum", "diagonalSum"]
[[[[0, 1, 2], [3, 4, 5], [6, 7, 8]]], [1], [4], [4], [8]]
Output:
[null, 6, 16, 16, 12]
Explanation:
- The grid is:
0 1 2
3 4 5
6 7 8
- adjacentSum(1): The cell with value 1 is at (0, 1). Its adjacent neighbors are 0, 2, and 4. Sum = 0 + 2 + 4 = 6.
- adjacentSum(4): The cell with value 4 is at (1, 1). Its adjacent neighbors are 1, 3, 5, and 7. Sum = 1 + 3 + 5 + 7 = 16.
- diagonalSum(4): The cell with value 4 is at (1, 1). Its diagonal neighbors are 0, 2, 6, and 8. Sum = 0 + 2 + 6 + 8 = 16.
- diagonalSum(8): The cell with value 8 is at (2, 2). Its diagonal neighbors are 4. Sum = 4.
Example 2:
Input:
["NeighborSum", "adjacentSum", "diagonalSum"]
[[[[1, 2, 0, 3], [4, 7, 15, 6], [8, 9, 10, 11], [12, 13, 14, 5]]], [15], [9]]
Output:
[null, 23, 45]
Explanation:
- The grid is:
1 2 0 3
4 7 15 6
8 9 10 11
12 13 14 5
- adjacentSum(15): The cell with value 15 is at (1, 2). Its adjacent neighbors are 0, 6, 7, and 10. Sum = 0 + 6 + 7 + 10 = 23.
- diagonalSum(9): The cell with value 9 is at (2, 1). Its diagonal neighbors are 4, 6, 12, and 14. Sum = 4 + 6 + 12 + 14 = 36.
Constraints
3 <= n <= 50
1 <= grid[i][j] <= n²
All values in the grid are unique.
0 <= value <= n² - 1
At most 2 * 10⁴ calls will be made to adjacentSum and diagonalSum.
Hash Map Position Lookup
Intuition Store the position (row, column) of each value in a hash map during initialization. For each query, look up the position in O(1) time and calculate the sum by checking valid neighbor positions.
Steps
- Create a hash map mapping each value to its (row, col) position
- For adjacentSum, check the 4 cardinal directions (up, down, left, right)
- For diagonalSum, check the 4 diagonal directions
- Only add values from valid positions within grid bounds
python
class NeighborSum:
def __init__(self, grid):
self.grid = grid
self.n = len(grid)
self.pos = {}
for i in range(self.n):
for j in range(self.n):
self.pos[grid[i][j]] = (i, j)
def adjacentSum(self, value):
i, j = self.pos[value]
total = 0
for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
ni, nj = i + di, j + dj
if 0 <= ni < self.n and 0 <= nj < self.n:
total += self.grid[ni][nj]
return total
def diagonalSum(self, value):
i, j = self.pos[value]
total = 0
for di, dj in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:
ni, nj = i + di, j + dj
if 0 <= ni < self.n and 0 <= nj < self.n:
total += self.grid[ni][nj]
return totalComplexity
- Time: O(n²) for initialization, O(1) for each query
- Space: O(n²) for storing positions
- Notes: Optimal balance between initialization and query time
Precomputed Sums
Intuition Precompute both adjacent and diagonal sums for all values during initialization. This makes each query a simple O(1) lookup at the cost of higher memory usage.
Steps
- Store position of each value in a hash map
- For each cell, calculate its adjacent sum and diagonal sum
- Store both sums in separate hash maps keyed by value
- Return precomputed sums directly for queries
python
class NeighborSum:
def __init__(self, grid):
self.n = len(grid)
self.adj_sum = {}
self.diag_sum = {}
for i in range(self.n):
for j in range(self.n):
value = grid[i][j]
adj_total = 0
diag_total = 0
for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
ni, nj = i + di, j + dj
if 0 <= ni < self.n and 0 <= nj < self.n:
adj_total += grid[ni][nj]
for di, dj in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:
ni, nj = i + di, j + dj
if 0 <= ni < self.n and 0 <= nj < self.n:
diag_total += grid[ni][nj]
self.adj_sum[value] = adj_total
self.diag_sum[value] = diag_total
def adjacentSum(self, value):
return self.adj_sum[value]
def diagonalSum(self, value):
return self.diag_sum[value]Complexity
- Time: O(n²) for initialization, O(1) for each query
- Space: O(n²) for storing precomputed sums
- Notes: Fastest query time but uses more memory than position lookup
Brute Force Grid Search
Intuition For each query, scan the entire grid to find the position of the value, then calculate the sum by checking neighbors. This avoids any preprocessing but has slower query time.
Steps
- Store the grid reference
- For each query, iterate through all cells to find the value’s position
- Once found, calculate the sum by checking valid neighbor positions
- Return the calculated sum
python
class NeighborSum:
def __init__(self, grid):
self.grid = grid
self.n = len(grid)
def _find_position(self, value):
for i in range(self.n):
for j in range(self.n):
if self.grid[i][j] == value:
return i, j
return -1, -1
def adjacentSum(self, value):
i, j = self._find_position(value)
total = 0
for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
ni, nj = i + di, j + dj
if 0 <= ni < self.n and 0 <= nj < self.n:
total += self.grid[ni][nj]
return total
def diagonalSum(self, value):
i, j = self._find_position(value)
total = 0
for di, dj in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:
ni, nj = i + di, j + dj
if 0 <= ni < self.n and 0 <= nj < self.n:
total += self.grid[ni][nj]
return totalComplexity
- Time: O(1) for initialization, O(n²) for each query
- Space: O(1) additional space
- Notes: Simplest implementation but inefficient for many queries