Design Neighbor Sum Service
Design Neighbor Sum Service is a easy design data structures problem solved with the pre-processing + tradeoffs pattern.
The best approach, optimal (precompute both sums), runs in O(n²) build, O(1) per query time and O(n²) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from scan for the value each time up.
Problem
Design a class built from an n × n grid of distinct values 0..n² - 1. It answers adjacentSum(value), the sum of the up/down/left/right neighbours of the cell holding value, and diagonalSum(value), the sum of its four diagonal neighbours. The theme is pre-processing vs query time.
Examples
Example 1
- Input
grid = [[0,1,2],[3,4,5],[6,7,8]]; adjacentSum(1); adjacentSum(4); diagonalSum(4); diagonalSum(8)- Output
6, 16, 16, 4- Why
- Neighbours of 4: 1, 3, 5, 7. Diagonals of 4: 0, 2, 6, 8.
Constraints
3 <= n <= 10; grid holds distinct values 0..n² - 1.- Up to 2n² calls.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (1 examples, or your own). Submit also runs 6 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Scan for the value each time | O(n²) per query | O(1) |
| Optimal (precompute both sums) | O(n²) build, O(1) per query | O(n²) |
1Scan for the value each time
O(n²) per queryO(1)On each query, search the grid for the value, then sum its neighbours.
- Locate value by scanning; add the 4 (or diagonal 4) neighbours within bounds.
class NeighborSum {
private final int[][] g;
public NeighborSum(int[][] grid) { g = grid; }
public int adjacentSum(int value) { return sum(value, new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }); }
public int diagonalSum(int value) { return sum(value, new int[][] { { -1, -1 }, { -1, 1 }, { 1, -1 }, { 1, 1 } }); }
private int sum(int value, int[][] dirs) {
int n = g.length;
for (int r = 0; r < n; r++)
for (int c = 0; c < n; c++)
if (g[r][c] == value) {
int s = 0;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nc >= 0 && nr < n && nc < n) s += g[nr][nc];
}
return s;
}
return 0;
}
}class NeighborSum:
def __init__(self, grid: List[List[int]]):
self.g = grid
def adjacentSum(self, value: int) -> int:
return self.sum(value, [(-1, 0), (1, 0), (0, -1), (0, 1)])
def diagonalSum(self, value: int) -> int:
return self.sum(value, [(-1, -1), (-1, 1), (1, -1), (1, 1)])
def sum(self, value: int, dirs: List[Tuple[int, int]]) -> int:
g = self.g
n = len(g)
for r in range(n):
for c in range(n):
if g[r][c] == value:
s = 0
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n:
s += g[nr][nc]
return s
return 0class NeighborSum {
vector<vector<int>> g;
int sum(int value, const vector<array<int, 2>>& dirs) {
int n = g.size();
for (int r = 0; r < n; r++)
for (int c = 0; c < n; c++)
if (g[r][c] == value) {
int s = 0;
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nc >= 0 && nr < n && nc < n) s += g[nr][nc];
}
return s;
}
return 0;
}
public:
NeighborSum(vector<vector<int>> grid) : g(grid) {}
int adjacentSum(int value) { return sum(value, { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }); }
int diagonalSum(int value) { return sum(value, { { -1, -1 }, { -1, 1 }, { 1, -1 }, { 1, 1 } }); }
};class NeighborSum {
constructor(grid) { this.g = grid; }
adjacentSum(value) { return this.sum(value, [[-1, 0], [1, 0], [0, -1], [0, 1]]); }
diagonalSum(value) { return this.sum(value, [[-1, -1], [-1, 1], [1, -1], [1, 1]]); }
sum(value, dirs) {
const g = this.g;
const n = g.length;
for (let r = 0; r < n; r++)
for (let c = 0; c < n; c++)
if (g[r][c] === value) {
let s = 0;
for (const d of dirs) {
const nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nc >= 0 && nr < n && nc < n) s += g[nr][nc];
}
return s;
}
return 0;
}
}2Optimal (precompute both sums)
O(n²) build, O(1) per queryO(n²)Values are exactly 0..n² - 1, so arrays indexed by value work. At construction, compute both sums for every value once. Every query is then O(1). The trade-off is more work up front and O(n²) memory.
- For each cell (r, c) with value v: adj[v] = sum of 4-neighbours; diag[v] = sum of diagonal neighbours.
- Queries return adj[value] and diag[value].
class NeighborSum {
private final int[] adj, diag;
public NeighborSum(int[][] grid) {
int n = grid.length;
adj = new int[n * n];
diag = new int[n * n];
for (int r = 0; r < n; r++)
for (int c = 0; c < n; c++)
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) continue;
int nr = r + dr, nc = c + dc;
if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
if (dr == 0 || dc == 0) adj[grid[r][c]] += grid[nr][nc];
else diag[grid[r][c]] += grid[nr][nc];
}
}
public int adjacentSum(int value) { return adj[value]; }
public int diagonalSum(int value) { return diag[value]; }
}class NeighborSum:
def __init__(self, grid: List[List[int]]):
n = len(grid)
self.adj = [0] * (n * n)
self.diag = [0] * (n * n)
for r in range(n):
for c in range(n):
for dr in range(-1, 2):
for dc in range(-1, 2):
if dr == 0 and dc == 0:
continue
nr, nc = r + dr, c + dc
if nr < 0 or nc < 0 or nr >= n or nc >= n:
continue
if dr == 0 or dc == 0:
self.adj[grid[r][c]] += grid[nr][nc]
else:
self.diag[grid[r][c]] += grid[nr][nc]
def adjacentSum(self, value: int) -> int:
return self.adj[value]
def diagonalSum(self, value: int) -> int:
return self.diag[value]class NeighborSum {
vector<int> adj, diag;
public:
NeighborSum(vector<vector<int>> grid) {
int n = grid.size();
adj.assign(n * n, 0);
diag.assign(n * n, 0);
for (int r = 0; r < n; r++)
for (int c = 0; c < n; c++)
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) continue;
int nr = r + dr, nc = c + dc;
if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
if (dr == 0 || dc == 0) adj[grid[r][c]] += grid[nr][nc];
else diag[grid[r][c]] += grid[nr][nc];
}
}
int adjacentSum(int value) { return adj[value]; }
int diagonalSum(int value) { return diag[value]; }
};class NeighborSum {
constructor(grid) {
const n = grid.length;
this.adj = new Array(n * n).fill(0);
this.diag = new Array(n * n).fill(0);
for (let r = 0; r < n; r++)
for (let c = 0; c < n; c++)
for (let dr = -1; dr <= 1; dr++)
for (let dc = -1; dc <= 1; dc++) {
if (dr === 0 && dc === 0) continue;
const nr = r + dr, nc = c + dc;
if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
if (dr === 0 || dc === 0) this.adj[grid[r][c]] += grid[nr][nc];
else this.diag[grid[r][c]] += grid[nr][nc];
}
}
adjacentSum(value) { return this.adj[value]; }
diagonalSum(value) { return this.diag[value]; }
}Edge cases to test
- Values on the border or in a corner (missing neighbours count as 0)
Hints
Hint 1
Finding a value by scanning costs O(n²) per call. Store where each value lives when the service starts.
FAQ
What is the best time complexity for Design Neighbor Sum Service?
Optimal (precompute both sums) runs in O(n²) build, O(1) per query time and O(n²) extra space.
Which pattern does Design Neighbor Sum Service use?
It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Simple Bank System, Design File System, Design HashMap.
Is there a brute force solution for Design Neighbor Sum Service?
Yes. Scan for the value each time takes O(n²) per query time and O(1) space. On each query, search the grid for the value, then sum its neighbours.
Which edge cases should I test for Design Neighbor Sum Service?
Values on the border or in a corner (missing neighbours count as 0).