Design Neighbor Sum Service
EasyPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Constructor: Store the input
gridand its dimensionnin member variables. findCoordinates(value)helper:- Iterate through each cell
(i, j)of the grid. - If
grid[i][j]matches thevalue, return the coordinates{i, j}.
- Iterate through each cell
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, addgrid[nr][nc]tosum. - Return
sum.
- Call
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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); */Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.