LeetCode Solutions Blog

Design Neighbor Sum Service

Difficulty: Easy

Problem Description

You are given a n x n 2D array grid containing distinct elements in the range [0, n^2 - 1]. Implement the NeighborSum class with methods to calculate the sum of adjacent and diagonal neighbors of a given value.

Key Insights

The grid is a square matrix (n x n) with distinct values.
Neighbors are defined based on their relative positions: adjacent neighbors are directly up, down, left, or right, while diagonal neighbors are at the corners surrounding a value.
Efficient access to neighbor sums requires knowing the position of each value in the grid.

Space and Time Complexity

Time Complexity: O(1) for both adjacentSum and diagonalSum after O(n^2) for initialization.
Space Complexity: O(n^2) for storing the grid and a mapping of values to their coordinates.

Solution

To solve the problem, we can use a 2D array to represent the grid and a hash table (dictionary) to map each value to its coordinates. The methods adjacentSum and diagonalSum will use these coordinates to calculate the sums by checking the valid indices for neighbors based on the predefined directions.

Code Solutions

class NeighborSum:
    def __init__(self, grid):
        self.grid = grid
        self.n = len(grid)
        self.value_to_position = {}
        
        # Map each value to its coordinates
        for i in range(self.n):
            for j in range(self.n):
                self.value_to_position[grid[i][j]] = (i, j)

    def adjacentSum(self, value):
        x, y = self.value_to_position[value]
        sum_adjacent = 0
        # Define adjacent positions
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # right, down, left, up
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < self.n and 0 <= ny < self.n:
                sum_adjacent += self.grid[nx][ny]
        
        return sum_adjacent

    def diagonalSum(self, value):
        x, y = self.value_to_position[value]
        sum_diagonal = 0
        # Define diagonal positions
        directions = [(1, 1), (1, -1), (-1, 1), (-1, -1)]  # bottom-right, bottom-left, top-right, top-left
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < self.n and 0 <= ny < self.n:
                sum_diagonal += self.grid[nx][ny]
        
        return sum_diagonal