LeetCode Solutions Blog

Design Neighbor Sum Service

Number: 3516

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an n x n grid with distinct elements in the range [0, n² - 1], implement a NeighborSum service that can efficiently compute:

The sum of adjacent neighbors (up, down, left, right) for a given value.
The sum of diagonal neighbors (top-left, top-right, bottom-left, bottom-right) for a given value.

Key Insights

Use a hash map (dictionary) to map each grid value to its corresponding (row, col) position for constant time lookups.
Define directional delta arrays for adjacent and diagonal neighbors.
Handle boundary conditions to ensure only valid grid indices are considered.
Preprocess the grid in O(n²) time so that each neighbor sum query can be answered in O(1) time.

Space and Time Complexity

Time Complexity: O(1) per query after O(n²) preprocessing. Space Complexity: O(n²) due to the value-to-coordinate mapping.

Solution

We start by preprocessing the grid to create a mapping from each value to its (row, col) location. This allows us to quickly locate the target value when a query is made. For each query (adjacentSum or diagonalSum), we:

Retrieve the coordinates of the given value using our map.
Iterate through the appropriate directional arrays (adjacent or diagonal).
Check if the neighbor coordinates are within the grid boundaries; if so, add the neighbor's value. This allows the neighbor sum operations to be computed in constant time, leveraging the preprocessing step.

Code Solutions

Below are code implementations in Python, JavaScript, C++, and Java.

class NeighborSum:
    def __init__(self, grid):
        # Store grid and dimensions, and preprocess to map value to (row, col)
        self.grid = grid
        self.n = len(grid)
        self.value_to_coords = {}
        for row in range(self.n):
            for col in range(self.n):
                self.value_to_coords[grid[row][col]] = (row, col)
    
    def adjacentSum(self, value):
        # Get the (row, col) for the given value
        if value not in self.value_to_coords:
            return 0
        row, col = self.value_to_coords[value]
        # Define adjacent directions: up, down, left, right.
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        total = 0
        for dr, dc in directions:
            newRow, newCol = row + dr, col + dc
            if 0 <= newRow < self.n and 0 <= newCol < self.n:
                total += self.grid[newRow][newCol]
        return total

    def diagonalSum(self, value):
        # Get the (row, col) for the given value
        if value not in self.value_to_coords:
            return 0
        row, col = self.value_to_coords[value]
        # Define diagonal directions: top-left, top-right, bottom-left, bottom-right.
        directions = [(-1, -1), (-1, 1), (1, -1), (1, 1)]
        total = 0
        for dr, dc in directions:
            newRow, newCol = row + dr, col + dc
            if 0 <= newRow < self.n and 0 <= newCol < self.n:
                total += self.grid[newRow][newCol]
        return total