Design Neighbor Sum Service - Practice Coding Problems

Design Neighbor Sum Service - Problem

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 with the given grid
int adjacentSum(int value) - returns the sum of elements adjacent to value (top, left, right, bottom neighbors)
int diagonalSum(int value) - returns the sum of elements diagonal to value (top-left, top-right, bottom-left, bottom-right neighbors)

The neighbors are calculated based on the position of value in the grid. If a neighbor position is out of bounds, it is ignored.

Input & Output

Example 1 — Basic Grid Operations

$ Input: grid = [[3,1,2],[1,4,4],[5,5,4]], operations = [["adjacentSum", 4], ["diagonalSum", 4]]

› Output: [9, 9]

💡 Note: For value 4 at position (1,1): adjacent neighbors are 1+2+1+5=9, diagonal neighbors are 3+2+5+4=14. But there are two 4's, so we get the first occurrence.

Example 2 — Edge Position

$ Input: grid = [[1,2,0,3],[4,7,15,6],[8,9,10,11],[12,13,14,5]], operations = [["adjacentSum", 15]]

› Output: [23]

💡 Note: Value 15 is at position (1,2). Adjacent neighbors: 2+0+6+10=18. Wait, let me recalculate: 7+0+6+10=23.

Example 3 — Corner Position

$ Input: grid = [[1,2],[3,4]], operations = [["diagonalSum", 1]]

› Output: [4]

💡 Note: Value 1 is at corner (0,0). Only one diagonal neighbor: bottom-right has value 4.

Constraints

3 ≤ n ≤ 10
0 ≤ grid[i][j] ≤ n² - 1
All values in grid are distinct
1 ≤ operations.length ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Grid

3×3 grid with distinct values [0, n²-1]

Preprocess

Map each value to its (row, col) position

Query Operations

Fast neighbor sum calculation using position lookup

Key Takeaway

🎯 Key Insight: Pre-compute value→position mapping once for O(1) position lookup during neighbor sum queries

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is to preprocess the grid once and map each value to its position for O(1) lookup. Best approach uses hash map preprocessing to store value→position mapping. Time: O(n²) preprocessing + O(1) per query, Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Preprocessing	O(n²) + O(q)	O(n²)	Pre-compute position map once, then O(1) neighbor sum calculation
Brute Force - Search Every Time	O(n² × q)	O(1)	Search the entire grid to find the value, then calculate neighbor sums

Hash Map Preprocessing — Algorithm Steps

Step 1: Build hash map from value to (row, col) position during initialization
Step 2: For each query, lookup position in O(1) time using hash map
Step 3: Check 4 adjacent or 4 diagonal neighbors and sum valid ones

Visualization

Tap to expand

Step-by-Step Walkthrough

Preprocessing

Build hash map: value → (row, col)

Fast Lookup

Get position in O(1) time

Calculate Sum

Check neighbors using position

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 50

typedef struct {
    int** grid;
    int n;
    int posMap[MAX_N * MAX_N][2];  // value -> [row, col]
} NeighborSum;

NeighborSum* createNeighborSum(int** grid, int n) {
    NeighborSum* ns = (NeighborSum*)malloc(sizeof(NeighborSum));
    ns->grid = grid;
    ns->n = n;
    
    // Precompute positions
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int value = grid[i][j];
            ns->posMap[value][0] = i;
            ns->posMap[value][1] = j;
        }
    }
    
    return ns;
}

int adjacentSum(NeighborSum* ns, int value) {
    int row = ns->posMap[value][0];
    int col = ns->posMap[value][1];
    
    // Calculate adjacent sum
    int directions[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    int total = 0;
    for (int i = 0; i < 4; i++) {
        int nr = row + directions[i][0];
        int nc = col + directions[i][1];
        if (nr >= 0 && nr < ns->n && nc >= 0 && nc < ns->n) {
            total += ns->grid[nr][nc];
        }
    }
    return total;
}

int diagonalSum(NeighborSum* ns, int value) {
    int row = ns->posMap[value][0];
    int col = ns->posMap[value][1];
    
    // Calculate diagonal sum
    int directions[4][2] = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
    int total = 0;
    for (int i = 0; i < 4; i++) {
        int nr = row + directions[i][0];
        int nc = col + directions[i][1];
        if (nr >= 0 && nr < ns->n && nc >= 0 && nc < ns->n) {
            total += ns->grid[nr][nc];
        }
    }
    return total;
}

int main() {
    int grid_data[3][3] = {{3,1,2},{1,4,4},{5,5,4}};
    int** grid = (int**)malloc(3 * sizeof(int*));
    for (int i = 0; i < 3; i++) {
        grid[i] = grid_data[i];
    }
    
    NeighborSum* ns = createNeighborSum(grid, 3);
    printf("[%d,%d]\n", adjacentSum(ns, 4), diagonalSum(ns, 4));
    
    free(ns);
    free(grid);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²) + O(q)

O(n²) preprocessing + O(1) per query × q queries

⚠ Quadratic Growth

Space Complexity

O(n²)

Hash map stores position for each of n² values

⚠ Quadratic Space

12.5K Views

Medium Frequency

~15 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Preprocessing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler