Problem statement

You are given an n x n grid whose cells hold the numbers 0 to n² - 1, each exactly once. Write the class NeighborSum:

• NeighborSum(int[][] grid) stores the grid.
• int adjacentSum(int value) returns the sum of the cells directly above, below, left and right of the cell holding value.
• int diagonalSum(int value) returns the sum of the cells diagonally next to the cell holding value (top-left, top-right, bottom-left, bottom-right).

Neighbours that would fall outside the grid are simply left out.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

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: 1 sits in the top row: its neighbours are 0, 2 and 4. 4 is the centre, with 1, 3, 5, 7 beside it and 0, 2, 6, 8 on its diagonals. 8 is a corner with a single diagonal neighbour, 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: 15 is at row 1, column 2: above it 0, below it 10, left 7, right 6. 9 is at row 2, column 1: its diagonals are 4, 15, 12 and 14.

Constraints

• 3 <= n == grid.length == grid[0].length <= 10
• 0 <= grid[i][j] <= n² - 1
• All grid[i][j] are distinct
• value in adjacentSum and diagonalSum is a number in the grid
• At most 2 * n² calls are made to adjacentSum and diagonalSum

Hints for Design Neighbor Sum Service

1. Hint 1

   Every query names a value, not a position — the first job is to find where that value is.

2. Hint 2

   Because the values are exactly 0 to n² - 1, you can record each value's row and column once, in the constructor.

3. Hint 3

   Then each query is four in-bounds checks around that position, with one list of offsets for the sides and one for the diagonals.

How to solve Design Neighbor Sum Service

Precompute where each value lives. The values are a permutation of 0 … n² - 1, so two arrays row[v] and col[v] turn every query into a constant number of neighbour checks.

Approach

1. In the constructor, for every cell (r, c) set row[grid[r][c]] = r and col[grid[r][c]] = c.
2. adjacentSum(value): from (row[value], col[value]), add the cells at offsets (-1,0), (1,0), (0,-1), (0,1) that are inside the grid.
3. diagonalSum(value): the same with offsets (-1,-1), (-1,1), (1,-1), (1,1).

Why it works

The lookup arrays are exact because each value appears in exactly one cell, and checking an offset against 0 <= y, x < n keeps precisely the neighbours that exist.

Complexity

• Time — O(n²) to build, O(1) per query
• Space — O(n²)

Pitfalls

• Scanning the whole grid for the value on every query works but costs O(n²) per call.
• Edge and corner cells have fewer neighbours — skip offsets that leave the grid rather than reading outside it.

Reference solution

Python

from typing import List

class NeighborSum:
    SIDES = ((-1, 0), (1, 0), (0, -1), (0, 1))
    DIAGONALS = ((-1, -1), (-1, 1), (1, -1), (1, 1))

    def __init__(self, grid: List[List[int]]):
        self.g = grid
        self.n = len(grid)
        self.pos = [None] * (self.n * self.n)
        for r in range(self.n):
            for c in range(self.n):
                self.pos[grid[r][c]] = (r, c)

    def _around(self, value: int, offsets) -> int:
        r, c = self.pos[value]
        s = 0
        for dr, dc in offsets:
            y, x = r + dr, c + dc
            if 0 <= y < self.n and 0 <= x < self.n:
                s += self.g[y][x]
        return s

    def adjacentSum(self, value: int) -> int:
        return self._around(value, self.SIDES)

    def diagonalSum(self, value: int) -> int:
        return self._around(value, self.DIAGONALS)

Java

class NeighborSum {
    private static final int[][] SIDES = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static final int[][] DIAGONALS = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
    private int[][] g;
    private int n;
    private int[] row, col;

    public NeighborSum(int[][] grid) {
        g = grid;
        n = grid.length;
        row = new int[n * n];
        col = new int[n * n];
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++) { row[grid[r][c]] = r; col[grid[r][c]] = c; }
    }

    private int around(int value, int[][] offsets) {
        int s = 0;
        for (int[] d : offsets) {
            int y = row[value] + d[0], x = col[value] + d[1];
            if (y >= 0 && y < n && x >= 0 && x < n) s += g[y][x];
        }
        return s;
    }

    public int adjacentSum(int value) {
        return around(value, SIDES);
    }

    public int diagonalSum(int value) {
        return around(value, DIAGONALS);
    }
}

C++

class NeighborSum {
    vector<vector<int>> g;
    int n;
    vector<int> row, col;

    int around(int value, const int (*offsets)[2]) {
        int s = 0;
        for (int k = 0; k < 4; k++) {
            int y = row[value] + offsets[k][0], x = col[value] + offsets[k][1];
            if (y >= 0 && y < n && x >= 0 && x < n) s += g[y][x];
        }
        return s;
    }
public:
    NeighborSum(vector<vector<int>>& grid) : g(grid), n((int)grid.size()), row(n * n), col(n * n) {
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++) { row[grid[r][c]] = r; col[grid[r][c]] = c; }
    }

    int adjacentSum(int value) {
        static const int sides[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        return around(value, sides);
    }

    int diagonalSum(int value) {
        static const int diagonals[4][2] = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
        return around(value, diagonals);
    }
};

JavaScript

var SIDES = [[-1, 0], [1, 0], [0, -1], [0, 1]];
var DIAGONALS = [[-1, -1], [-1, 1], [1, -1], [1, 1]];

var NeighborSum = function(grid) {
    this.g = grid;
    this.n = grid.length;
    this.row = [];
    this.col = [];
    for (var r = 0; r < this.n; r++)
        for (var c = 0; c < this.n; c++) { this.row[grid[r][c]] = r; this.col[grid[r][c]] = c; }
};

NeighborSum.prototype.around = function(value, offsets) {
    var s = 0;
    for (var k = 0; k < 4; k++) {
        var y = this.row[value] + offsets[k][0], x = this.col[value] + offsets[k][1];
        if (y >= 0 && y < this.n && x >= 0 && x < this.n) s += this.g[y][x];
    }
    return s;
};

NeighborSum.prototype.adjacentSum = function(value) {
    return this.around(value, SIDES);
};

NeighborSum.prototype.diagonalSum = function(value) {
    return this.around(value, DIAGONALS);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy
• Convert Sorted Array to Binary Search Tree Easy