Start practising

Design Neighbor Sum Service

Easy Design Data Structures Pre-processing + tradeoffs Original on LeetCode

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, 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.

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 Java code.

ApproachTimeSpace
Scan for the value each timeO(n²) per queryO(1)
Optimal (precompute both sums)O(n²) build, O(1) per queryO(n²)

1Scan for the value each time

TimeO(n²) per query
SpaceO(1)

On each query, search the grid for the value, then sum its neighbours.

  1. Locate value by scanning; add the 4 (or diagonal 4) neighbours within bounds.
Java
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;
    }
}

2Optimal (precompute both sums)

TimeO(n²) build, O(1) per query
SpaceO(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.

  1. For each cell (r, c) with value v: adj[v] = sum of 4-neighbours; diag[v] = sum of diagonal neighbours.
  2. Queries return adj[value] and diag[value].
Java
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]; }
}

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.

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).