3242. Design Neighbor Sum Service

Problem¶

Given an \(n \times n\) grid containing each value from \(0\) to \(n^2-1\) exactly once, support queries for the sum of a value's orthogonal or diagonal neighbors.

grid = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
adjacentSum(4) -> 16  # 1 + 3 + 5 + 7
diagonalSum(8) -> 4   # 4

class NeighborSum:
    def __init__(self, grid: list[list[int]]):
        pass

    def adjacentSum(self, value: int) -> int:
        pass

    def diagonalSum(self, value: int) -> int:
        pass

Key trick¶

Precompute each value's position. Then a query checks only four cells instead of searching the grid.

Trap¶

Check both row and column bounds, especially for values on an edge or corner.

Why is it interesting?¶

The grid is distinct, consecutive values allow a list-based position lookup, turning repeated queries into constant-time operations.

Python solution¶

class NeighborSum:
    def __init__(self, grid: list[list[int]]):
        self.grid = grid
        self.n = len(grid)
        self.pos = [(0, 0)] * (self.n * self.n)

        for r in range(self.n):
            for c in range(self.n):
                self.pos[grid[r][c]] = (r, c)

    def _sum(self, value: int, directions: tuple[tuple[int, int], ...]) -> int:
        r, c = self.pos[value]
        total = 0

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < self.n and 0 <= nc < self.n:
                total += self.grid[nr][nc]

        return total

    def adjacentSum(self, value: int) -> int:
        return self._sum(value, ((-1, 0), (1, 0), (0, -1), (0, 1)))

    def diagonalSum(self, value: int) -> int:
        return self._sum(value, ((-1, -1), (-1, 1), (1, -1), (1, 1)))

Preprocessing takes \(O(n^2)\) time and space. Each query takes \(O(1)\) time.

Comment on my solution¶

Your solution is correct and has optimal query time. The loop that appends each row to self.grid is unnecessary: assigning self.grid = grid has the same reference-sharing behavior. Also, initializing self.index with zeros is harmless because every entry is replaced, but initializing it with coordinate pairs better reflects its contents.

class NeighborSum:

    def __init__(self, grid: list[list[int]]):
        self.n = len(grid)
        self.grid = []
        self.index = [0] * (self.n * self.n)
        for row in grid:
            self.grid.append(row)
        for r in range(self.n):
            for c in range(self.n):
                self.index[grid[r][c]] = (r,c)

    def adjacentSum(self, value: int) -> int:
        r, c = self.index[value]
        total = 0
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < self.n and 0 <= nc < self.n:
                total += self.grid[nr][nc]
        return total

    def diagonalSum(self, value: int) -> int:
        r, c = self.index[value]
        total = 0
        for dr, dc in ((-1, -1), (-1, 1), (1, -1), (1, 1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < self.n and 0 <= nc < self.n:
                total += self.grid[nr][nc]
        return total