# Design Neighbor Sum Service
**Difficulty:** EASY
[External](https://leetcode.com/problems/design-neighbor-sum-service)
Canonical: https://scaleengineer.com/dsa/problems/design-neighbor-sum-service
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Array, Hash Table, Matrix
---
## 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 of `value`, that is either to the top, left, right, or bottom of `value` in `grid`.
* `int diagonalSum(int value)` returns the **sum** of elements which are diagonal neighbors of `value`, that is either to the top-left, top-right, bottom-left, or bottom-right of `value` in `grid`.

![](https://assets.glich.co/dsa/design-neighbor-sum-service/image0.png)

**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:**

**![](https://assets.glich.co/dsa/design-neighbor-sum-service/image1.png)**

* 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:**

**![](https://assets.glich.co/dsa/design-neighbor-sum-service/image2.png)**

* 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 <= 10`
* `0 <= grid[i][j] <= n2 - 1`
* All `grid[i][j]` are distinct.
* `value` in `adjacentSum` and `diagonalSum` will be in the range `[0, n2 - 1]`.
* At most `2 * n2` calls will be made to `adjacentSum` and `diagonalSum`.

# Approaches
## Brute-Force Search on Each Call
This straightforward approach involves storing the grid and, for each query, performing a linear scan of the entire grid to locate the given `value`. Once the coordinates are found, it calculates the sum of the requested neighbors by checking the adjacent or diagonal cells.
**Time:** O(n<sup>2</sup>) for each query (`adjacentSum` or `diagonalSum`). The dominant operation is finding the coordinates of the `value`, which requires scanning the entire grid. The constructor is O(1). · **Space:** O(n<sup>2</sup>) to store the grid. No significant extra space is used.
**Pros:** Simple to understand and implement.; Minimal memory usage beyond storing the grid.; No setup cost in the constructor.
**Cons:** Highly inefficient for multiple queries as the grid is scanned repeatedly.; The time complexity per query is high, making it unsuitable for larger grids or frequent calls.
### Explanation
The implementation consists of two main parts. The constructor simply stores the grid. The query methods (`adjacentSum` and `diagonalSum`) first call a helper function to find the `(row, col)` of the `value`. This search iterates through all `n*n` cells. After finding the location, it iterates through a predefined set of relative offsets (e.g., `(-1, 0)` for top neighbor) to find valid neighbors, sums their values, and returns the result. While simple, this method is inefficient due to the repeated grid traversal.

```java
class NeighborSum {
    private int[][] grid;
    private int n;

    public NeighborSum(int[][] grid) {
        this.grid = grid;
        this.n = grid.length;
    }

    private int[] findCoordinates(int value) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == value) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1}; // Should not be reached
    }

    public int adjacentSum(int value) {
        int[] coords = findCoordinates(value);
        int r = coords[0];
        int c = coords[1];
        int sum = 0;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int[] dir : directions) {
            int nr = r + dir[0];
            int nc = c + dir[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                sum += grid[nr][nc];
            }
        }
        return sum;
    }

    public int diagonalSum(int value) {
        int[] coords = findCoordinates(value);
        int r = coords[0];
        int c = coords[1];
        int sum = 0;
        int[][] directions = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

        for (int[] dir : directions) {
            int nr = r + dir[0];
            int nc = c + dir[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                sum += grid[nr][nc];
            }
        }
        return sum;
    }
}
```
### Algorithm
- **Constructor**: Store the input `grid` and its dimension `n` in member variables.
- **`findCoordinates(value)` helper**:
  - Iterate through each cell `(i, j)` of the grid.
  - If `grid[i][j]` matches the `value`, return the coordinates `{i, j}`.
- **`adjacentSum(value)` / `diagonalSum(value)`**:
  - Call `findCoordinates(value)` to get the location `(r, c)`.
  - Initialize `sum = 0`.
  - Define an array of relative offsets for adjacent or diagonal neighbors.
  - Loop through each offset `(dr, dc)`.
  - Calculate neighbor coordinates `(nr, nc) = (r + dr, c + dc)`.
  - If `(nr, nc)` is within the grid boundaries, add `grid[nr][nc]` to `sum`.
  - Return `sum`.

## Pre-computation with a Lookup Table
This optimized approach trades initial setup time and memory for constant-time queries. During initialization, it pre-processes the grid to create a lookup table that maps each grid value to its `(row, col)` coordinates. Subsequent calls to `adjacentSum` or `diagonalSum` can then find the location of a value in O(1) time.
**Time:** O(n<sup>2</sup>) for the constructor to build the lookup table. Each query (`adjacentSum` or `diagonalSum`) is O(1) because finding coordinates and summing neighbors are both constant-time operations. · **Space:** O(n<sup>2</sup>). This includes O(n<sup>2</sup>) for the grid and O(n<sup>2</sup>) for the `locations` lookup table.
**Pros:** Extremely fast O(1) query time.; Efficient for scenarios with many repeated queries.; The overall time complexity is dominated by the one-time setup.
**Cons:** Requires extra space for the lookup table.; Incurs a one-time O(n<sup>2</sup>) setup cost in the constructor, which might be undesirable if only a few queries are made.
### Explanation
The key to this approach is the `locations` lookup table. Since the grid values are distinct and range from `0` to `n*n - 1`, a simple array can be used for this purpose. The constructor iterates through the grid once to populate this `locations` array. For any given `value`, `locations[value]` will instantly provide its coordinates. The query methods use this O(1) lookup to get the coordinates and then proceed to calculate the sum of neighbors, which is also a constant-time operation as it involves checking at most 8 cells.

```java
class NeighborSum {
    private int[][] grid;
    private int n;
    private int[][] locations;

    public NeighborSum(int[][] grid) {
        this.grid = grid;
        this.n = grid.length;
        this.locations = new int[n * n][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int val = grid[i][j];
                this.locations[val][0] = i;
                this.locations[val][1] = j;
            }
        }
    }

    public int adjacentSum(int value) {
        int r = locations[value][0];
        int c = locations[value][1];
        int sum = 0;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int[] dir : directions) {
            int nr = r + dir[0];
            int nc = c + dir[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                sum += grid[nr][nc];
            }
        }
        return sum;
    }

    public int diagonalSum(int value) {
        int r = locations[value][0];
        int c = locations[value][1];
        int sum = 0;
        int[][] directions = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

        for (int[] dir : directions) {
            int nr = r + dir[0];
            int nc = c + dir[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                sum += grid[nr][nc];
            }
        }
        return sum;
    }
}
```
### Algorithm
- **Constructor**:
  - Store the input `grid` and its dimension `n`.
  - Initialize a `locations` array of size `n*n` to store coordinates.
  - Iterate through each cell `(i, j)` of the grid.
  - For the value `val = grid[i][j]`, set `locations[val] = {i, j}`.
- **`adjacentSum(value)` / `diagonalSum(value)`**:
  - Get the coordinates `(r, c)` of `value` in O(1) time from `locations[value]`.
  - Initialize `sum = 0`.
  - Define an array of relative offsets for adjacent or diagonal neighbors.
  - Loop through each offset `(dr, dc)`.
  - Calculate neighbor coordinates `(nr, nc) = (r + dr, c + dc)`.
  - If `(nr, nc)` is within the grid boundaries, add `grid[nr][nc]` to `sum`.
  - Return `sum`.

# Solutions
### Java

```java
class neighborSum { private int [][] grid ; private final Map < Integer , int []> d = new HashMap <>(); private final int [][] dirs = { {- 1 , 0 , 1 , 0 , - 1 }, {- 1 , 1 , 1 , - 1 , - 1 } }; public neighborSum ( int [][] grid ) { this . grid = grid ; int m = grid . length , n = grid [ 0 ]. length ; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { d . put ( grid [ i ][ j ], new int [] { i , j }); } } } public int adjacentSum ( int value ) { return cal ( value , 0 ); } public int diagonalSum ( int value ) { return cal ( value , 1 ); } private int cal ( int value , int k ) { int [] p = d . get ( value ); int s = 0 ; for ( int q = 0 ; q < 4 ; ++ q ) { int x = p [ 0 ] + dirs [ k ][ q ], y = p [ 1 ] + dirs [ k ][ q + 1 ]; if ( x >= 0 && x < grid . length && y >= 0 && y < grid [ 0 ]. length ) { s += grid [ x ][ y ]; } } return s ; } } /** * Your neighborSum object will be instantiated and called as such: * neighborSum obj = new neighborSum(grid); * int param_1 = obj.adjacentSum(value); * int param_2 = obj.diagonalSum(value); */
```

### CPP

```cpp
class neighborSum { public: neighborSum ( vector < vector < int >>& grid ) { this -> grid = grid ; int m = grid . size (), n = grid [ 0 ]. size (); for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { d [ grid [ i ][ j ]] = { i , j }; } } } int adjacentSum ( int value ) { return cal ( value , 0 ); } int diagonalSum ( int value ) { return cal ( value , 1 ); } private: vector < vector < int >> grid ; unordered_map < int , pair < int , int >> d ; int dirs [ 2 ][ 5 ] = { { - 1 , 0 , 1 , 0 , - 1 }, { - 1 , 1 , 1 , - 1 , - 1 } }; int cal ( int value , int k ) { auto [ i , j ] = d [ value ]; int s = 0 ; for ( int q = 0 ; q < 4 ; ++ q ) { int x = i + dirs [ k ][ q ], y = j + dirs [ k ][ q + 1 ]; if ( x >= 0 && x < grid . size () && y >= 0 && y < grid [ 0 ]. size ()) { s += grid [ x ][ y ]; } } return s ; } }; /** * Your neighborSum object will be instantiated and called as such: * neighborSum* obj = new neighborSum(grid); * int param_1 = obj->adjacentSum(value); * int param_2 = obj->diagonalSum(value); */
```

### Python

```python
class neighborSum : def __init__ ( self , grid : List [ List [ int ]]): self . grid = grid self . d = {} self . dirs = (( - 1 , 0 , 1 , 0 , - 1 ), ( - 1 , 1 , 1 , - 1 , - 1 )) for i , row in enumerate ( grid ): for j , x in enumerate ( row ): self . d [ x ] = ( i , j ) def adjacentSum ( self , value : int ) -> int : return self . cal ( value , 0 ) def cal ( self , value : int , k : int ): i , j = self . d [ value ] s = 0 for a , b in pairwise ( self . dirs [ k ]): x , y = i + a , j + b if 0 <= x < len ( self . grid ) and 0 <= y < len ( self . grid [ 0 ]): s += self . grid [ x ][ y ] return s def diagonalSum ( self , value : int ) -> int : return self . cal ( value , 1 ) # Your neighborSum object will be instantiated and called as such: # obj = neighborSum(grid) # param_1 = obj.adjacentSum(value) # param_2 = obj.diagonalSum(value)
```