LeetCode 3242 - Design Neighbor Sum Service
The problem asks us to design a service that works on a square matrix, where every value in the matrix is unique. For any given value, we must efficiently compute two different types of neighbor sums.
Difficulty: 🟢 Easy
Topics: Array, Hash Table, Design, Matrix, Simulation
Solution
Problem Understanding
The problem asks us to design a service that works on a square matrix, where every value in the matrix is unique. For any given value, we must efficiently compute two different types of neighbor sums.
The first operation, adjacentSum(value), returns the sum of all directly adjacent cells. These are the four cardinal directions:
- Top
- Bottom
- Left
- Right
The second operation, diagonalSum(value), returns the sum of all diagonal neighbors:
- Top-left
- Top-right
- Bottom-left
- Bottom-right
The matrix contains all distinct values in the range [0, n^2 - 1], which means every value appears exactly once. This guarantee is important because it allows us to map each value directly to a unique position in the grid.
The input to the constructor is a 2D matrix grid. After initialization, multiple queries may be performed asking for adjacent or diagonal sums for specific values.
The expected output for each query is simply the sum of valid neighboring cells. If a neighbor would go outside the matrix boundaries, it is ignored.
The constraints are small:
3 <= n <= 10- At most
2 * n^2queries
Even though the constraints are tiny, the problem is fundamentally about designing a clean and efficient lookup structure. A naive implementation would repeatedly scan the matrix to locate a value before computing its neighbors. A better design preprocesses the grid once and enables constant-time lookups afterward.
Several edge cases are important:
- Corner cells only have two adjacent neighbors and one diagonal neighbor.
- Edge cells have fewer neighbors than interior cells.
- Diagonal and adjacent neighbor sets are completely separate.
- Every value is guaranteed to exist in the grid.
- Values are distinct, so there is no ambiguity when locating a value.
Approaches
Brute Force Approach
A straightforward solution is to scan the entire matrix every time a query is made.
For adjacentSum(value):
- Traverse the matrix to find the coordinates of
value. - Check the four adjacent directions.
- Add all valid neighbors.
For diagonalSum(value):
- Again traverse the matrix to locate
value. - Check the four diagonal directions.
- Add all valid neighbors.
This approach is correct because eventually we find the target cell and examine all required neighboring positions.
However, locating the value requires O(n^2) time for every query. Since multiple queries may be issued, this repeated scanning is unnecessary.
Optimal Approach
The key observation is that all values are unique.
Because each value appears exactly once, we can preprocess the matrix and store:
value -> (row, col)
in a hash map.
Then each query becomes:
- Look up the coordinates in
O(1) - Check the four relevant directions
- Sum valid neighbors
Since there are always at most four adjacent and four diagonal neighbors, each query becomes constant time.
This is the ideal design-oriented solution because we trade a small amount of preprocessing space for extremely fast queries.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) per query | O(1) | Scans entire matrix for every lookup |
| Optimal | O(1) per query after preprocessing | O(n²) | Uses hash map from value to coordinates |
Algorithm Walkthrough
Optimal Algorithm
- Store the grid and its size inside the class.
We need access to the original matrix for neighbor lookups and boundary checks. 2. Build a hash map from value to coordinates.
Traverse the entire matrix once. For every cell (r, c), store:
position[grid[r][c]] = (r, c)
This allows constant-time lookup of any value's location. 3. Define the four adjacent directions.
These are:
(-1, 0) # top
(1, 0) # bottom
(0, -1) # left
(0, 1) # right
- For
adjacentSum(value):
-
Retrieve the coordinates from the hash map.
-
Visit all four adjacent directions.
-
For each candidate cell:
-
Check whether it lies inside the matrix.
-
If valid, add its value to the sum.
- Define the four diagonal directions.
These are:
(-1, -1)
(-1, 1)
(1, -1)
(1, 1)
- For
diagonalSum(value):
- Retrieve the coordinates from the hash map.
- Visit all four diagonal positions.
- Add all valid neighbors.
Why it works
The algorithm works because every value uniquely maps to exactly one coordinate in the matrix. The preprocessing step guarantees that we can instantly locate any queried value. Once the coordinates are known, the only remaining task is checking a constant number of neighboring positions. Boundary checks ensure that invalid coordinates outside the matrix are ignored, so the computed sum always matches the problem definition.
Python Solution
from typing import List
class NeighborSum:
def __init__(self, grid: List[List[int]]):
self.grid = grid
self.n = len(grid)
# Map value -> (row, col)
self.position = {}
for r in range(self.n):
for c in range(self.n):
self.position[grid[r][c]] = (r, c)
def adjacentSum(self, value: int) -> int:
row, col = self.position[value]
directions = [
(-1, 0), # top
(1, 0), # bottom
(0, -1), # left
(0, 1), # right
]
total = 0
for dr, dc in directions:
nr = row + dr
nc = col + dc
if 0 <= nr < self.n and 0 <= nc < self.n:
total += self.grid[nr][nc]
return total
def diagonalSum(self, value: int) -> int:
row, col = self.position[value]
directions = [
(-1, -1),
(-1, 1),
(1, -1),
(1, 1),
]
total = 0
for dr, dc in directions:
nr = row + dr
nc = col + dc
if 0 <= nr < self.n and 0 <= nc < self.n:
total += self.grid[nr][nc]
return total
The constructor performs all preprocessing work. It stores the matrix size and creates a dictionary mapping each value to its coordinates.
The adjacentSum method first retrieves the position of the queried value in constant time. It then iterates through the four cardinal directions and checks whether each neighboring coordinate remains inside the matrix bounds. Valid neighbors contribute to the running sum.
The diagonalSum method follows the exact same structure, but uses diagonal direction offsets instead.
The implementation is intentionally simple because the problem constraints are small and the logic naturally fits a direct simulation approach.
Go Solution
package main
type NeighborSum struct {
grid [][]int
n int
position map[int][2]int
}
func Constructor(grid [][]int) NeighborSum {
n := len(grid)
position := make(map[int][2]int)
for r := 0; r < n; r++ {
for c := 0; c < n; c++ {
position[grid[r][c]] = [2]int{r, c}
}
}
return NeighborSum{
grid: grid,
n: n,
position: position,
}
}
func (this *NeighborSum) AdjacentSum(value int) int {
row := this.position[value][0]
col := this.position[value][1]
directions := [][2]int{
{-1, 0},
{1, 0},
{0, -1},
{0, 1},
}
total := 0
for _, dir := range directions {
nr := row + dir[0]
nc := col + dir[1]
if nr >= 0 && nr < this.n && nc >= 0 && nc < this.n {
total += this.grid[nr][nc]
}
}
return total
}
func (this *NeighborSum) DiagonalSum(value int) int {
row := this.position[value][0]
col := this.position[value][1]
directions := [][2]int{
{-1, -1},
{-1, 1},
{1, -1},
{1, 1},
}
total := 0
for _, dir := range directions {
nr := row + dir[0]
nc := col + dir[1]
if nr >= 0 && nr < this.n && nc >= 0 && nc < this.n {
total += this.grid[nr][nc]
}
}
return total
}
/**
* Your NeighborSum object will be instantiated and called as such:
* obj := Constructor(grid)
* param_1 := obj.AdjacentSum(value)
* param_2 := obj.DiagonalSum(value)
*/
The Go implementation mirrors the Python solution closely. The primary difference is that Go uses a map[int][2]int to store coordinates. Arrays of fixed size two are convenient for representing (row, col) pairs.
Go slices are used for the direction arrays, and explicit boundary checks are required before accessing grid elements.
Integer overflow is not a concern because the maximum possible sum is very small under the given constraints.
Worked Examples
Example 1
Input:
grid = [
[0,1,2],
[3,4,5],
[6,7,8]
]
Preprocessing
The position map becomes:
| Value | Position |
|---|---|
| 0 | (0,0) |
| 1 | (0,1) |
| 2 | (0,2) |
| 3 | (1,0) |
| 4 | (1,1) |
| 5 | (1,2) |
| 6 | (2,0) |
| 7 | (2,1) |
| 8 | (2,2) |
Query: adjacentSum(1)
Value 1 is located at (0,1).
Check adjacent neighbors:
| Direction | Coordinate | Valid | Value |
|---|---|---|---|
| Top | (-1,1) | No | - |
| Bottom | (1,1) | Yes | 4 |
| Left | (0,0) | Yes | 0 |
| Right | (0,2) | Yes | 2 |
Total:
4 + 0 + 2 = 6
Query: adjacentSum(4)
Value 4 is located at (1,1).
| Direction | Coordinate | Value |
|---|---|---|
| Top | (0,1) | 1 |
| Bottom | (2,1) | 7 |
| Left | (1,0) | 3 |
| Right | (1,2) | 5 |
Total:
1 + 7 + 3 + 5 = 16
Query: diagonalSum(4)
| Direction | Coordinate | Value |
|---|---|---|
| Top-left | (0,0) | 0 |
| Top-right | (0,2) | 2 |
| Bottom-left | (2,0) | 6 |
| Bottom-right | (2,2) | 8 |
Total:
0 + 2 + 6 + 8 = 16
Query: diagonalSum(8)
Value 8 is at (2,2).
| Direction | Coordinate | Valid | Value |
|---|---|---|---|
| Top-left | (1,1) | Yes | 4 |
| Top-right | (1,3) | No | - |
| Bottom-left | (3,1) | No | - |
| Bottom-right | (3,3) | No | - |
Total:
4
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n²) preprocessing, O(1) per query | Hash map construction scans matrix once, each query checks at most 4 neighbors |
| Space | O(n²) | Hash map stores one coordinate pair per value |
The preprocessing phase visits every matrix cell exactly once, producing O(n²) initialization cost. Each query examines a constant number of neighboring positions, so both query methods run in constant time. The extra space comes from storing the coordinate mapping for every matrix value.
Test Cases
from typing import List
class NeighborSum:
def __init__(self, grid: List[List[int]]):
self.grid = grid
self.n = len(grid)
self.position = {}
for r in range(self.n):
for c in range(self.n):
self.position[grid[r][c]] = (r, c)
def adjacentSum(self, value: int) -> int:
row, col = self.position[value]
directions = [
(-1, 0),
(1, 0),
(0, -1),
(0, 1),
]
total = 0
for dr, dc in directions:
nr = row + dr
nc = col + dc
if 0 <= nr < self.n and 0 <= nc < self.n:
total += self.grid[nr][nc]
return total
def diagonalSum(self, value: int) -> int:
row, col = self.position[value]
directions = [
(-1, -1),
(-1, 1),
(1, -1),
(1, 1),
]
total = 0
for dr, dc in directions:
nr = row + dr
nc = col + dc
if 0 <= nr < self.n and 0 <= nc < self.n:
total += self.grid[nr][nc]
return total
# Example 1
grid1 = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8]
]
obj1 = NeighborSum(grid1)
assert obj1.adjacentSum(1) == 6 # top edge cell
assert obj1.adjacentSum(4) == 16 # center cell
assert obj1.diagonalSum(4) == 16 # center diagonals
assert obj1.diagonalSum(8) == 4 # corner diagonal
# Example 2
grid2 = [
[1, 2, 0, 3],
[4, 7, 15, 6],
[8, 9, 10, 11],
[12, 13, 14, 5]
]
obj2 = NeighborSum(grid2)
assert obj2.adjacentSum(15) == 23 # mixed neighbors
assert obj2.diagonalSum(9) == 45 # four diagonal neighbors
# Corner case
grid3 = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8]
]
obj3 = NeighborSum(grid3)
assert obj3.adjacentSum(0) == 4 # only right and bottom
assert obj3.diagonalSum(0) == 4 # only bottom-right diagonal
# Edge but not corner
assert obj3.adjacentSum(2) == 6 # top-right corner
assert obj3.diagonalSum(2) == 4 # only bottom-left diagonal
# Center with maximum neighbors
assert obj3.adjacentSum(4) == 16 # all four adjacent
assert obj3.diagonalSum(4) == 16 # all four diagonal
# Larger grid
grid4 = [
[0, 1, 2, 3],
[4, 5, 6, 7],
[8, 9, 10, 11],
[12, 13, 14, 15]
]
obj4 = NeighborSum(grid4)
assert obj4.adjacentSum(10) == 40 # interior cell
assert obj4.diagonalSum(10) == 40 # interior diagonals
| Test | Why |
|---|---|
| Example 1 | Validates all basic operations |
| Example 2 | Tests non-sequential arrangement |
| Corner cell queries | Ensures boundary handling works |
| Edge cell queries | Verifies partial neighbor sets |
| Center cell queries | Confirms all four neighbors are included |
| Larger grid | Tests scalability and indexing correctness |
Edge Cases
Corner Cells
Corner cells are the most restrictive positions in the matrix because many neighboring directions fall outside the grid. For example, the top-left corner has only two adjacent neighbors and one diagonal neighbor. A buggy implementation might accidentally access invalid indices or include nonexistent cells in the sum.
This implementation prevents that problem using explicit boundary checks:
0 <= nr < self.n and 0 <= nc < self.n
Only valid coordinates contribute to the total.
Edge Cells
Cells on the border but not in the corner have three adjacent neighbors and two diagonal neighbors. These cases are easy to mishandle because some directions are valid while others are not.
The algorithm handles this naturally by evaluating every candidate direction independently and including only coordinates that remain inside bounds.
Non-Sequential Value Placement
The values in the matrix are distinct, but they are not guaranteed to appear in sorted order. A naive implementation that assumes arithmetic relationships between values and coordinates would fail.
The preprocessing hash map completely avoids this issue. Every value explicitly stores its exact coordinates, so lookup correctness does not depend on matrix ordering.