Skip to main content
Talentd

Design Neighbor Sum Service - Solution & Explanation

EasyArrayHash TableDesignMatrix16 min read
Practice this problem

Problem Statement

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.

 

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

Approach Overview

Problem Overview: You are given an n x n grid of unique values and must design a service that returns the sum of neighbors around a specific value. Two queries are supported: the sum of the four adjacent cells (up, down, left, right) and the sum of the four diagonal neighbors. The challenge is locating the value quickly and computing neighbor sums efficiently.

Approach 1: Direct Index Lookup (O(1) time per query, O(n²) space)

The key observation is that the grid values are unique. During initialization, iterate through the matrix and store each value’s coordinates in a hash map like value → (row, col). When a query arrives, perform a constant-time lookup to find the cell location. From that position, check the four adjacent or four diagonal directions and accumulate valid values while ensuring indices stay within bounds. Each query performs a fixed number of checks, so both adjacentSum and diagonalSum run in O(1) time with O(n²) preprocessing storage for the mapping.

This approach relies heavily on fast coordinate retrieval using a hash table combined with directional traversal in a matrix. It’s simple to implement and ideal when the service receives many queries after initialization.

Approach 2: Precomputed Neighbor Arrays (O(1) queries, O(n²) preprocessing)

Another strategy is to precompute both neighbor sums during initialization. After building the value → position mapping, iterate over every cell in the grid and calculate its adjacent and diagonal sums immediately. Store these results in two arrays or maps keyed by value: one for adjacent sums and one for diagonal sums. Each query simply returns the stored result using a constant-time lookup.

The preprocessing step scans the grid once and performs constant directional checks for each cell, giving O(n²) initialization time and O(n²) space. After that, both operations run in strict O(1) time with no additional computation. This technique trades a bit more preprocessing work for extremely fast queries and cleaner runtime logic.

Conceptually, this solution mixes array traversal with a lightweight design pattern where expensive work happens during initialization rather than during queries.

Recommended for interviews: Direct Index Lookup is typically the expected solution. It demonstrates awareness that unique values allow a hash map for constant-time coordinate lookup. Implementing boundary checks and directional traversal shows strong fundamentals with matrices while keeping the implementation concise.

Approach 1: Approach 1: Direct Index Lookup

This approach directly finds the position of the element in the grid and checks its adjacent or diagonal cells. Using the element's coordinates, it sums up the appropriate neighbors by checking boundary conditions. This approach has a guaranteed complexity due to the small size limits of the grid (n ≤ 10).

The NeighborSum class is initialized with the grid and populates a dictionary to map each value to its coordinates. For adjacentSum and diagonalSum, the stored references allow fast lookup of neighbors by iterating over potential offsets.

Code

PythonCC++JavaC#JavaScript

Python

C

C++

Java

C#

JavaScript

Complexity

Time Complexity: Each operation to find neighbors is O(1) due to fixed offsets and small grid size.
Space Complexity: O(n^2) for storing the grid and positions.

Try this approach in the editor →

Approach 2: Approach 2: Precomputed Neighbor Arrays

In this approach, we construct precomputed lists for each element that contain all potential adjacent and diagonal sums. These lists are cached, allowing for rapid retrieval of sums without the need to recompute directions dynamically.

The preprocessing step compiles possible sums of neighbors during initialization, effectively converting neighbor sum requests into dictionary lookups for constant time retrieval.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(1) for lookups; grid initialized in O(n^2).
Space Complexity: O(n^2) as additional maps store precomputed sums.

Try this approach in the editor →

Approach 3: Hash Table

We can use a hash table d to store the coordinates of each element. Then, according to the problem description, we separately calculate the sum of adjacent elements and diagonally adjacent elements.

In terms of time complexity, initializing the hash table has a time complexity of O(m times n), and calculating the sum of adjacent elements and diagonally adjacent elements has a time complexity of O(1). The space complexity is O(m times n).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Direct Index Lookup

Time Complexity: Each operation to find neighbors is O(1) due to fixed offsets and small grid size.
Space Complexity: O(n^2) for storing the grid and positions.

Approach 2: Precomputed Neighbor Arrays

Time Complexity: O(1) for lookups; grid initialized in O(n^2).
Space Complexity: O(n^2) as additional maps store precomputed sums.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Index LookupO(n²) init, O(1) per queryO(n²)Best general solution when many queries are expected and you want simple constant-time lookups
Precomputed Neighbor ArraysO(n²) preprocessing, O(1) per queryO(n²)Useful when query performance must be minimal and you prefer returning precomputed results

Video Solution

leetcode 3242 : design neigbor sum service : python solution • leetcode blind 75 • 310 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Design Neighbor Sum Service easy or hard?
Design Neighbor Sum Service is classified as an Easy problem. The main challenge is recognizing that unique grid values allow constant-time coordinate lookup using a hash map, making neighbor calculations straightforward.
Design Neighbor Sum Service Python/Java solution
The Python and Java implementations both follow the same idea: build a HashMap or dictionary mapping values to their matrix coordinates, then compute neighbor sums using directional offsets. Each query runs in O(1) time after preprocessing.
How to solve Design Neighbor Sum Service in O(1)?
Store the coordinates of each grid value in a hash map during initialization. When a query asks for a value, retrieve its position instantly and examine the four adjacent or four diagonal directions with boundary checks. Because only a constant number of cells are examined, the query runs in O(1) time.
What is the best approach for Design Neighbor Sum Service?
The most practical solution uses a hash map that stores value → (row, column) coordinates during initialization. Each query performs a constant-time lookup to locate the value and then checks the four adjacent or diagonal positions. This keeps query time O(1) with O(n²) preprocessing space.
Is Design Neighbor Sum Service asked at Google/Amazon/Meta?
Problems involving matrix traversal, hash maps, and lightweight system design patterns are common in interviews at companies like Amazon and Google. While this exact problem may vary, similar tasks that combine grid indexing with constant-time lookups frequently appear in coding rounds.
What data structure is used in Design Neighbor Sum Service?
The core data structure is a hash table mapping each grid value to its coordinates. The grid itself is stored as a 2D array or matrix, and directional offsets are used to check neighboring cells efficiently.
What is the time complexity of Design Neighbor Sum Service?
Initialization requires scanning the entire grid once, which takes O(n²) time. Each query—either adjacentSum or diagonalSum—checks at most four cells, so the runtime per query is O(1). Space complexity is O(n²) due to the value-to-position mapping.

Ready to solve this problem?

Practice Design Neighbor Sum Service with our built-in code editor and test cases.

Practice on FleetCode
Previous

Array With Elements Not Equal to Average of Neighbors

Next

Matrix Block Sum