Design Neighbor Sum Service solution and explanation
The problem
You are given a n x n 2D array grid containing distinct elements in the range [0, n2 - 1].
Implement the NeighborSum class:
NeighborSum(int [][]grid)initializes the object.int adjacentSum(int value)returns the sum of elements which are adjacent neighbors ofvalue, that is either to the top, left, right, or bottom ofvalueingrid.int diagonalSum(int value)returns the sum of elements which are diagonal neighbors ofvalue, that is either to the top-left, top-right, bottom-left, or bottom-right ofvalueingrid.
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, 4]
Explanation:
- The adjacent neighbors of 1 are 0, 2, and 4.
- The adjacent neighbors of 4 are 1, 3, 5, and 7.
- The diagonal neighbors of 4 are 0, 2, 6, and 8.
- The diagonal neighbor of 8 is 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 adjacent neighbors of 15 are 0, 10, 7, and 6.
- The diagonal neighbors of 9 are 4, 12, 14, and 15.
Constraints:
3 <= n == grid.length == grid[0].length <= 100 <= grid[i][j] <= n2 - 1- All
grid[i][j]are distinct. valueinadjacentSumanddiagonalSumwill be in the range[0, n2 - 1].- At most
2 * n2calls will be made toadjacentSumanddiagonalSum.
Approach overview
Problem Overview: You are given an n x n grid of unique values and must design a service that returns the sum of neighbors around a specific value. Two queries are supported: the sum of the four adjacent cells (up, down, left, right) and the sum of the four diagonal neighbors. The challenge is locating the value quickly and computing neighbor sums efficiently.
Approach 1: Direct Index Lookup (O(1) time per query, O(n²) space)
The key observation is that the grid values are unique. During initialization, iterate through the matrix and store each value’s coordinates in a hash map like value → (row, col). When a query arrives, perform a constant-time lookup to find the cell location. From that position, check the four adjacent or four diagonal directions and accumulate valid values while ensuring indices stay within bounds. Each query performs a fixed number of checks, so both adjacentSum and diagonalSum run in O(1) time with O(n²) preprocessing storage for the mapping.
This approach relies heavily on fast coordinate retrieval using a hash table combined with directional traversal in a matrix. It’s simple to implement and ideal when the service receives many queries after initialization.
Approach 2: Precomputed Neighbor Arrays (O(1) queries, O(n²) preprocessing)
Another strategy is to precompute both neighbor sums during initialization. After building the value → position mapping, iterate over every cell in the grid and calculate its adjacent and diagonal sums immediately. Store these results in two arrays or maps keyed by value: one for adjacent sums and one for diagonal sums. Each query simply returns the stored result using a constant-time lookup.
The preprocessing step scans the grid once and performs constant directional checks for each cell, giving O(n²) initialization time and O(n²) space. After that, both operations run in strict O(1) time with no additional computation. This technique trades a bit more preprocessing work for extremely fast queries and cleaner runtime logic.
Conceptually, this solution mixes array traversal with a lightweight design pattern where expensive work happens during initialization rather than during queries.
Recommended for interviews: Direct Index Lookup is typically the expected solution. It demonstrates awareness that unique values allow a hash map for constant-time coordinate lookup. Implementing boundary checks and directional traversal shows strong fundamentals with matrices while keeping the implementation concise.
Approach 1: Approach 1: Direct Index Lookup
This approach directly finds the position of the element in the grid and checks its adjacent or diagonal cells. Using the element's coordinates, it sums up the appropriate neighbors by checking boundary conditions. This approach has a guaranteed complexity due to the small size limits of the grid (n ≤ 10).
class NeighborSum:
def __init__(self, grid):
self.grid = grid
self.n = len(grid)
self.position = {grid[i][j]: (i, j) for i in range(self.n) for j in range(self.n)}
def adjacentSum(self, value):
r, c = self.position[value]
adj = 0
for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < self.n and 0 <= nc < self.n:
adj += self.grid[nr][nc]
return adj
def diagonalSum(self, value):
r, c = self.position[value]
diag = 0
for dr, dc in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < self.n and 0 <= nc < self.n:
diag += self.grid[nr][nc]
return diagimport java.util.HashMap;
import java.util.Map;
class NeighborSum {
private int[][] grid;
private int n;
private Map<Integer, int[]> position;
public NeighborSum(int[][] grid) {
this.grid = grid;
this.n = grid.length;
this.position = new HashMap<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
position.put(grid[i][j], new int[]{i, j});
}
}
}
public int adjacentSum(int value) {
int[] pos = position.get(value);
int r = pos[0], c = pos[1];
int sum = 0;
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (int[] d : directions) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n)
sum += grid[nr][nc];
}
return sum;
}
public int diagonalSum(int value) {
int[] pos = position.get(value);
int r = pos[0], c = pos[1];
int sum = 0;
int[][] directions = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
for (int[] d : directions) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n)
sum += grid[nr][nc];
}
return sum;
}
}#include <vector>
#include <unordered_map>
using namespace std;
class NeighborSum {
vector<vector<int>> grid;
unordered_map<int, pair<int, int>> position;
int n;
public:
NeighborSum(vector<vector<int>>& grid) : grid(grid) {
n = grid.size();
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
position[grid[i][j]] = {i, j};
}
int adjacentSum(int value) {
auto [r, c] = position[value];
int sum = 0;
vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (auto [dr, dc] : directions) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n)
sum += grid[nr][nc];
}
return sum;
}
int diagonalSum(int value) {
auto [r, c] = position[value];
int sum = 0;
vector<pair<int, int>> directions = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
for (auto [dr, dc] : directions) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n)
sum += grid[nr][nc];
}
return sum;
}
};class NeighborSum {
constructor(grid) {
this.grid = grid;
this.n = grid.length;
this.position = new Map();
grid.forEach((row, i) => {
row.forEach((val, j) => {
this.position.set(val, [i, j]);
});
});
}
adjacentSum(value) {
const [r, c] = this.position.get(value);
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
let sum = 0;
for (const [dr, dc] of directions) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < this.n && nc >= 0 && nc < this.n) {
sum += this.grid[nr][nc];
}
}
return sum;
}
diagonalSum(value) {
const [r, c] = this.position.get(value);
const directions = [[1, 1], [1, -1], [-1, 1], [-1, -1]];
let sum = 0;
for (const [dr, dc] of directions) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < this.n && nc >= 0 && nc < this.n) {
sum += this.grid[nr][nc];
}
}
return sum;
}
}#include <stdlib.h>
typedef struct {
int** grid;
int n;
int* position;
} NeighborSum;
NeighborSum* neighborSumCreate(int** grid, int gridSize, int* gridColSize) {
NeighborSum* obj = malloc(sizeof(NeighborSum));
obj->grid = grid;
obj->n = gridSize;
obj->position = malloc(gridSize * gridSize * sizeof(int) * 2);
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < gridSize; j++) {
int value = grid[i][j];
obj->position[value * 2] = i;
obj->position[value * 2 + 1] = j;
}
}
return obj;
}
int adjacentSum(NeighborSum* obj, int value) {
int r = obj->position[value * 2];
int c = obj->position[value * 2 + 1];
int sum = 0;
int directions[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
for (int i = 0; i < 4; i++) {
int nr = r + directions[i][0];
int nc = c + directions[i][1];
if (nr >= 0 && nr < obj->n && nc >= 0 && nc < obj->n) {
sum += obj->grid[nr][nc];
}
}
return sum;
}
int diagonalSum(NeighborSum* obj, int value) {
int r = obj->position[value * 2];
int c = obj->position[value * 2 + 1];
int sum = 0;
int directions[4][2] = {{1,1},{1,-1},{-1,1},{-1,-1}};
for (int i = 0; i < 4; i++) {
int nr = r + directions[i][0];
int nc = c + directions[i][1];
if (nr >= 0 && nr < obj->n && nc >= 0 && nc < obj->n) {
sum += obj->grid[nr][nc];
}
}
return sum;
}
void neighborSumFree(NeighborSum* obj) {
if (obj) {
free(obj->position);
free(obj);
}
}using System;
using System.Collections.Generic;
public class NeighborSum {
private int[,] grid;
private int n;
private Dictionary<int, (int, int)> position;
public NeighborSum(int[,] grid) {
this.grid = grid;
this.n = grid.GetLength(0);
position = new Dictionary<int, (int, int)>();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
position[grid[i, j]] = (i, j);
}
public int AdjacentSum(int value) {
var (r, c) = position[value];
int sum = 0;
int[,] directions = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
for (int i = 0; i < 4; i++) {
int nr = r + directions[i, 0], nc = c + directions[i, 1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n)
sum += grid[nr, nc];
}
return sum;
}
public int DiagonalSum(int value) {
var (r, c) = position[value];
int sum = 0;
int[,] directions = { { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };
for (int i = 0; i < 4; i++) {
int nr = r + directions[i, 0], nc = c + directions[i, 1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n)
sum += grid[nr, nc];
}
return sum;
}
}The NeighborSum class is initialized with the grid and populates a dictionary to map each value to its coordinates. For adjacentSum and diagonalSum, the stored references allow fast lookup of neighbors by iterating over potential offsets.
Time Complexity: Each operation to find neighbors is O(1) due to fixed offsets and small grid size.
Space Complexity: O(n^2) for storing the grid and positions.
Approach 2: Approach 2: Precomputed Neighbor Arrays
In this approach, we construct precomputed lists for each element that contain all potential adjacent and diagonal sums. These lists are cached, allowing for rapid retrieval of sums without the need to recompute directions dynamically.
class NeighborSum:
def __init__(self, grid):
self.grid = grid
self.n = len(grid)
self.pos_to_adj = {}
self.pos_to_diag = {}
# Precompute the sums
for i in range(self.n):
for j in range(self.n):
value = grid[i][j]
self.pos_to_adj[value] = self._compute_adjacent(i, j)
self.pos_to_diag[value] = self._compute_diagonal(i, j)
def _compute_adjacent(self, r, c):
adj = 0
for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < self.n and 0 <= nc < self.n:
adj += self.grid[nr][nc]
return adj
def _compute_diagonal(self, r, c):
diag = 0
for dr, dc in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < self.n and 0 <= nc < self.n:
diag += self.grid[nr][nc]
return diag
def adjacentSum(self, value):
return self.pos_to_adj[value]
def diagonalSum(self, value):
return self.pos_to_diag[value]#include <vector>
#include <unordered_map>
using namespace std;
class NeighborSum {
vector<vector<int>> grid;
unordered_map<int, int> adjSumMap;
unordered_map<int, int> diagSumMap;
int n;
int computeAdjacent(int r, int c) {
int sum = 0;
vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (auto [dr, dc] : directions) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n)
sum += grid[nr][nc];
}
return sum;
}
int computeDiagonal(int r, int c) {
int sum = 0;
vector<pair<int, int>> directions = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
for (auto [dr, dc] : directions) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n)
sum += grid[nr][nc];
}
return sum;
}
public:
NeighborSum(vector<vector<int>>& grid) : grid(grid) {
n = grid.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int value = grid[i][j];
adjSumMap[value] = computeAdjacent(i, j);
diagSumMap[value] = computeDiagonal(i, j);
}
}
}
int adjacentSum(int value) {
return adjSumMap[value];
}
int diagonalSum(int value) {
return diagSumMap[value];
}
};The preprocessing step compiles possible sums of neighbors during initialization, effectively converting neighbor sum requests into dictionary lookups for constant time retrieval.
Time Complexity: O(1) for lookups; grid initialized in O(n^2).
Space Complexity: O(n^2) as additional maps store precomputed sums.
Approach 3: Hash Table
We can use a hash table d to store the coordinates of each element. Then, according to the problem description, we separately calculate the sum of adjacent elements and diagonally adjacent elements.
In terms of time complexity, initializing the hash table has a time complexity of O(m times n), and calculating the sum of adjacent elements and diagonally adjacent elements has a time complexity of O(1). The space complexity is O(m times n).
class NeighborSum {
private grid: number[][];
private d: Map<number, [number, number]> = new Map();
private dirs: number[][] = [
[-1, 0, 1, 0, -1],
[-1, 1, 1, -1, -1],
];
constructor(grid: number[][]) {
for (let i = 0; i < grid.length; ++i) {
for (let j = 0; j < grid[0].length; ++j) {
this.d.set(grid[i][j], [i, j]);
}
}
this.grid = grid;
}
adjacentSum(value: number): number {
return this.cal(value, 0);
}
diagonalSum(value: number): number {
return this.cal(value, 1);
}
cal(value: number, k: number): number {
const [i, j] = this.d.get(value)!;
let s = 0;
for (let q = 0; q < 4; ++q) {
const [x, y] = [i + this.dirs[k][q], j + this.dirs[k][q + 1]];
if (x >= 0 && x < this.grid.length && y >= 0 && y < this.grid[0].length) {
s += this.grid[x][y];
}
}
return s;
}
}
/**
* Your NeighborSum object will be instantiated and called as such:
* var obj = new NeighborSum(grid)
* var param_1 = obj.adjacentSum(value)
* var param_2 = obj.diagonalSum(value)
*/type NeighborSum struct {
grid [][]int
d map[int][2]int
dirs [2][5]int
}
func Constructor(grid [][]int) NeighborSum {
d := map[int][2]int{}
for i, row := range grid {
for j, x := range row {
d[x] = [2]int{i, j}
}
}
dirs := [2][5]int{{-1, 0, 1, 0, -1}, {-1, 1, 1, -1, -1}}
return NeighborSum{grid, d, dirs}
}
func (this *NeighborSum) AdjacentSum(value int) int {
return this.cal(value, 0)
}
func (this *NeighborSum) DiagonalSum(value int) int {
return this.cal(value, 1)
}
func (this *NeighborSum) cal(value, k int) int {
p := this.d[value]
s := 0
for q := 0; q < 4; q++ {
x, y := p[0]+this.dirs[k][q], p[1]+this.dirs[k][q+1]
if x >= 0 && x < len(this.grid) && y >= 0 && y < len(this.grid[0]) {
s += this.grid[x][y]
}
}
return s
}
/**
* Your NeighborSum object will be instantiated and called as such:
* obj := Constructor(grid);
* param_1 := obj.AdjacentSum(value);
* param_2 := obj.DiagonalSum(value);
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Direct Index Lookup | Time Complexity: Each operation to find neighbors is O(1) due to fixed offsets and small grid size. |
| Approach 2: Precomputed Neighbor Arrays | Time Complexity: O(1) for lookups; grid initialized in O(n^2). |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Index Lookup | O(n²) init, O(1) per query | O(n²) | Best general solution when many queries are expected and you want simple constant-time lookups |
| Precomputed Neighbor Arrays | O(n²) preprocessing, O(1) per query | O(n²) | Useful when query performance must be minimal and you prefer returning precomputed results |
Frequently asked questions
Is Design Neighbor Sum Service easy or hard?
Design Neighbor Sum Service is classified as an Easy problem. The main challenge is recognizing that unique grid values allow constant-time coordinate lookup using a hash map, making neighbor calculations straightforward.
Design Neighbor Sum Service Python/Java solution
The Python and Java implementations both follow the same idea: build a HashMap or dictionary mapping values to their matrix coordinates, then compute neighbor sums using directional offsets. Each query runs in O(1) time after preprocessing.
How to solve Design Neighbor Sum Service in O(1)?
Store the coordinates of each grid value in a hash map during initialization. When a query asks for a value, retrieve its position instantly and examine the four adjacent or four diagonal directions with boundary checks. Because only a constant number of cells are examined, the query runs in O(1) time.
What is the best approach for Design Neighbor Sum Service?
The most practical solution uses a hash map that stores value → (row, column) coordinates during initialization. Each query performs a constant-time lookup to locate the value and then checks the four adjacent or diagonal positions. This keeps query time O(1) with O(n²) preprocessing space.
Is Design Neighbor Sum Service asked at Google/Amazon/Meta?
Problems involving matrix traversal, hash maps, and lightweight system design patterns are common in interviews at companies like Amazon and Google. While this exact problem may vary, similar tasks that combine grid indexing with constant-time lookups frequently appear in coding rounds.
What data structure is used in Design Neighbor Sum Service?
The core data structure is a hash table mapping each grid value to its coordinates. The grid itself is stored as a 2D array or matrix, and directional offsets are used to check neighboring cells efficiently.
What is the time complexity of Design Neighbor Sum Service?
Initialization requires scanning the entire grid once, which takes O(n²) time. Each query—either adjacentSum or diagonalSum—checks at most four cells, so the runtime per query is O(1). Space complexity is O(n²) due to the value-to-position mapping.