LeetCode #3242 — EASY

Design Neighbor Sum Service

Build confidence with an intuition-first walkthrough focused on array fundamentals.

Solve on LeetCode

The Problem

Problem Statement

You are given a n x n 2D array grid containing distinct elements in the range [0, n² - 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] <= n² - 1
All grid[i][j] are distinct.
value in adjacentSum and diagonalSum will be in the range [0, n² - 1].
At most 2 * n² calls will be made to adjacentSum and diagonalSum.

Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Hash Map · Design

Example 1

["NeighborSum","adjacentSum","adjacentSum","diagonalSum","diagonalSum"]
[[[[0,1,2],[3,4,5],[6,7,8]]],[1],[4],[4],[8]]

Example 2

["NeighborSum","adjacentSum","diagonalSum"]
[[[[1,2,0,3],[4,7,15,6],[8,9,10,11],[12,13,14,5]]],[15],[9]]

Core Insight

What unlocks the optimal approach

Find the cell <code>(i, j)</code> in which the element is present.
You can store the coordinates for each value.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3242: Design Neighbor Sum Service
class NeighborSum {
    private int[][] grid;
    private final Map<Integer, int[]> d = new HashMap<>();
    private final int[][] dirs = {{-1, 0, 1, 0, -1}, {-1, 1, 1, -1, -1}};

    public NeighborSum(int[][] grid) {
        this.grid = grid;
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                d.put(grid[i][j], new int[] {i, j});
            }
        }
    }

    public int adjacentSum(int value) {
        return cal(value, 0);
    }

    public int diagonalSum(int value) {
        return cal(value, 1);
    }

    private int cal(int value, int k) {
        int[] p = d.get(value);
        int s = 0;
        for (int q = 0; q < 4; ++q) {
            int x = p[0] + dirs[k][q], y = p[1] + dirs[k][q + 1];
            if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length) {
                s += grid[x][y];
            }
        }
        return s;
    }
}

/**
 * Your NeighborSum object will be instantiated and called as such:
 * NeighborSum obj = new NeighborSum(grid);
 * int param_1 = obj.adjacentSum(value);
 * int param_2 = obj.diagonalSum(value);
 */

// Accepted solution for LeetCode #3242: Design Neighbor Sum Service
type NeighborSum struct {
	grid [][]int
	d    map[int][2]int
	dirs [2][5]int
}

func Constructor(grid [][]int) NeighborSum {
	d := map[int][2]int{}
	for i, row := range grid {
		for j, x := range row {
			d[x] = [2]int{i, j}
		}
	}
	dirs := [2][5]int{{-1, 0, 1, 0, -1}, {-1, 1, 1, -1, -1}}
	return NeighborSum{grid, d, dirs}
}

func (this *NeighborSum) AdjacentSum(value int) int {
	return this.cal(value, 0)
}

func (this *NeighborSum) DiagonalSum(value int) int {
	return this.cal(value, 1)
}

func (this *NeighborSum) cal(value, k int) int {
	p := this.d[value]
	s := 0
	for q := 0; q < 4; q++ {
		x, y := p[0]+this.dirs[k][q], p[1]+this.dirs[k][q+1]
		if x >= 0 && x < len(this.grid) && y >= 0 && y < len(this.grid[0]) {
			s += this.grid[x][y]
		}
	}
	return s
}

/**
 * Your NeighborSum object will be instantiated and called as such:
 * obj := Constructor(grid);
 * param_1 := obj.AdjacentSum(value);
 * param_2 := obj.DiagonalSum(value);
 */

# Accepted solution for LeetCode #3242: Design Neighbor Sum Service
class NeighborSum:

    def __init__(self, grid: List[List[int]]):
        self.grid = grid
        self.d = {}
        self.dirs = ((-1, 0, 1, 0, -1), (-1, 1, 1, -1, -1))
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                self.d[x] = (i, j)

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

    def cal(self, value: int, k: int):
        i, j = self.d[value]
        s = 0
        for a, b in pairwise(self.dirs[k]):
            x, y = i + a, j + b
            if 0 <= x < len(self.grid) and 0 <= y < len(self.grid[0]):
                s += self.grid[x][y]
        return s

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


# Your NeighborSum object will be instantiated and called as such:
# obj = NeighborSum(grid)
# param_1 = obj.adjacentSum(value)
# param_2 = obj.diagonalSum(value)

// Accepted solution for LeetCode #3242: Design Neighbor Sum Service
/**
 * [3242] Design Neighbor Sum Service
 */
pub struct Solution {}

// submission codes start here

struct NeighborSum {
    adjacent_values: Vec<i32>,
    diagonal_values: Vec<i32>,
}

const DIAGONAL_DELTA: [(i32, i32); 4] = [(-1, 1), (1, 1), (1, -1), (-1, -1)];
const ADJACENT_DELTA: [(i32, i32); 4] = [(-1, 0), (0, 1), (0, -1), (1, 0)];

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl NeighborSum {
    fn new(grid: Vec<Vec<i32>>) -> Self {
        let n = grid.len();
        let mut adjacent_values = vec![0; n * n];
        let mut diagonal_values = vec![0; n * n];
        let n = n as i32;

        for i in 0..n {
            for j in 0..n {
                let mut adjacent_value = 0;
                let mut diagonal_value = 0;
                for (&(x_1, y_1), &(x_2, y_2)) in ADJACENT_DELTA.iter().zip(DIAGONAL_DELTA.iter()) {
                    let (x, y) = (i + x_1, j + y_1);

                    if x >= 0 && x < n && y >= 0 && y < n {
                        adjacent_value += grid[x as usize][y as usize];
                    }

                    let (x, y) = (i + x_2, j + y_2);

                    if x >= 0 && x < n && y >= 0 && y < n {
                        diagonal_value += grid[x as usize][y as usize];
                    }
                }
                adjacent_values[grid[i as usize][j as usize] as usize] = adjacent_value;
                diagonal_values[grid[i as usize][j as usize] as usize] = diagonal_value;
            }
        }

        Self {
            adjacent_values,
            diagonal_values,
        }
    }

    fn adjacent_sum(&self, value: i32) -> i32 {
        self.adjacent_values[value as usize]
    }

    fn diagonal_sum(&self, value: i32) -> i32 {
        self.diagonal_values[value as usize]
    }
}

/**
 * Your NeighborSum object will be instantiated and called as such:
 * let obj = NeighborSum::new(grid);
 * let ret_1: i32 = obj.adjacent_sum(value);
 * let ret_2: i32 = obj.diagonal_sum(value);
 */

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_3242() {
        let sum = NeighborSum::new(vec![vec![0, 1, 2], vec![3, 4, 5], vec![6, 7, 8]]);

        assert_eq!(6, sum.adjacent_sum(1));
        assert_eq!(16, sum.adjacent_sum(4));
        assert_eq!(16, sum.diagonal_sum(4));
        assert_eq!(4, sum.diagonal_sum(8));
    }
}

// Accepted solution for LeetCode #3242: Design Neighbor Sum Service
class NeighborSum {
    private grid: number[][];
    private d: Map<number, [number, number]> = new Map();
    private dirs: number[][] = [
        [-1, 0, 1, 0, -1],
        [-1, 1, 1, -1, -1],
    ];
    constructor(grid: number[][]) {
        for (let i = 0; i < grid.length; ++i) {
            for (let j = 0; j < grid[0].length; ++j) {
                this.d.set(grid[i][j], [i, j]);
            }
        }
        this.grid = grid;
    }

    adjacentSum(value: number): number {
        return this.cal(value, 0);
    }

    diagonalSum(value: number): number {
        return this.cal(value, 1);
    }

    cal(value: number, k: number): number {
        const [i, j] = this.d.get(value)!;
        let s = 0;
        for (let q = 0; q < 4; ++q) {
            const [x, y] = [i + this.dirs[k][q], j + this.dirs[k][q + 1]];
            if (x >= 0 && x < this.grid.length && y >= 0 && y < this.grid[0].length) {
                s += this.grid[x][y];
            }
        }
        return s;
    }
}

/**
 * Your NeighborSum object will be instantiated and called as such:
 * var obj = new NeighborSum(grid)
 * var param_1 = obj.adjacentSum(value)
 * var param_2 = obj.diagonalSum(value)
 */

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(1) per op

Space

O(n)

Approach Breakdown

NAIVE

O(n) per op time

O(n) space

Use a simple list or array for storage. Each operation (get, put, remove) requires a linear scan to find the target element — O(n) per operation. Space is O(n) to store the data. The linear search makes this impractical for frequent operations.

OPTIMIZED DESIGN

O(1) per op time

O(n) space

Design problems target O(1) amortized per operation by combining data structures (hash map + doubly-linked list for LRU, stack + min-tracking for MinStack). Space is always at least O(n) to store the data. The challenge is achieving constant-time operations through clever structure composition.

Shortcut: Combine two data structures to get O(1) for each operation type. Space is always O(n).

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Mutating counts without cleanup

Wrong move: Zero-count keys stay in map and break distinct/count constraints.

Usually fails on: Window/map size checks are consistently off by one.

Fix: Delete keys when count reaches zero.