Design Neighbor Sum Service - Video Solutions

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.