3242. Design Neighbor Sum Service

EasyDesignArrayHash TableMatrixSimulation

Problem Description

You are given an n x n 2D array grid containing distinct elements in the range [0, n^2 - 1]. The task is to implement a NeighborSum class with the following functionalities:

NeighborSum(int [][]grid): Initializes the object with a given grid.
int adjacentSum(int value): Returns the sum of the elements adjacent to value, meaning the elements directly to the top, left, right, or bottom.
int diagonalSum(int value): Returns the sum of elements diagonally adjacent to value, which are either to the top-left, top-right, bottom-left, or bottom-right of value.

Intuition

The solution leverages a hash table to map each element in the grid to its coordinates. By doing so, the lookup for any element's position in the grid becomes efficient. When we need to calculate the sum of adjacent or diagonal neighbors:

Hash Table for Fast Lookup: Utilize a hash table to store the coordinates of each element in the grid right after initialization. This allows quick access to any element's location.
Define Directions: Use predefined directions to navigate through adjacent and diagonal neighbors. These directions need to be carefully defined based on what neighbor's positions you want to calculate—either adjacent (for adjacentSum) or diagonal (for diagonalSum).
Efficient Calculation: For computing the sum, iterate over each possible direction from the current position (obtained via the hash table). Check if the new position is valid, i.e., it is within the grid bounds, and if valid, add the value at this position to the sum.

Thus, this approach allows efficient computation of the desired sums by directly accessing neighbors and summing their values.

Solution Approach

The solution approach is built around the use of a hash table and directional navigation to efficiently compute the sums:

Hash Table Mapping:
- We first create a hash table d where each key is a value from the grid, and its corresponding value is a tuple (i, j), representing the element's coordinates in the grid.
- This initial mapping is done during the initialization of the NeighborSum object, ensuring that any position can be retrieved in constant time.
Direction Arrays:
- Two sets of direction arrays are employed. The dirs[0] is used for calculating adjacent sums, specifying movements in the order of north, east, south, and west. The dirs[1] array helps in navigating diagonally, covering positions like north-west, north-east, south-east, and south-west.
Sum Calculation Function (cal):
- The cal function is a common utility used by both adjacentSum and diagonalSum. It retrieves the position of value from the hash table.
- Utilizing the direction arrays according to whether the adjacent or diagonal sum is required, it checks the validity of each neighboring position. If valid (within bounds), it adds the corresponding value from grid to the cumulative sum.
Method Implementations:
- adjacentSum: Calls the cal function with a direction index 0, leveraging it for calculating sums of immediate neighbors.
- diagonalSum: Calls the same function with a direction index 1, catering to diagonal neighbor sums.

This approach efficiently manages the navigation and sum calculation by combining fast look-up with directional traversal across the grid.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple 3x3 grid as an example to illustrate how the NeighborSum class functions:

grid = [
  [8, 1, 6],
  [3, 5, 7],
  [4, 9, 2]
]

Initialization:
- When the NeighborSum object is initialized with the above grid, a hash table d is constructed to map each element to its coordinates:
  - d = {8: (0, 0), 1: (0, 1), 6: (0, 2), 3: (1, 0), 5: (1, 1), 7: (1, 2), 4: (2, 0), 9: (2, 1), 2: (2, 2)}
Direction Arrays:
- For adjacency:
  - adjacent_dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)], corresponding to movements north, south, west, and east, respectively.
- For diagonals:
  - diagonal_dirs = [(-1, -1), (-1, 1), (1, 1), (1, -1)], corresponding to movements north-west, north-east, south-east, and south-west, respectively.
Calculating Adjacent Sum for value = 5:
- Find position of 5 using our map: (i, j) = (1, 1).
- For each direction in adjacent_dirs, check if the resultant position is within bounds:
  - (0, 1) (north): valid, value = 1
  - (2, 1) (south): valid, value = 9
  - (1, 0) (west): valid, value = 3
  - (1, 2) (east): valid, value = 7
- Sum of adjacent elements = 1 + 9 + 3 + 7 = 20
Calculating Diagonal Sum for value = 5:
- Retrieve position (1, 1) again from the hash table.
- Check each diagonal direction:
  - (0, 0) (north-west): valid, value = 8
  - (0, 2) (north-east): valid, value = 6
  - (2, 2) (south-east): valid, value = 2
  - (2, 0) (south-west): valid, value = 4
- Sum of diagonal elements = 8 + 6 + 2 + 4 = 20

This walkthrough exemplifies how the NeighborSum class efficiently uses position mapping and direction arrays to find the sums of adjacent and diagonal elements for any given value in the grid.

Solution Implementation

1from typing import List
2
3class NeighborSum:
4    def __init__(self, grid: List[List[int]]):
5        # Initialize with the given grid
6        self.grid = grid
7        # Dictionary to store the coordinates of each value in the grid
8        self.position_map = {}
9        # Directions for calculating sums: [up, right, down, left] and diagonal directions
10        self.directions = ((-1, 0, 1, 0), (0, 1, 0, -1)), ((-1, 1, 1, -1), (1, 1, -1, -1))
11      
12        # Populate the position_map with coordinates of each value
13        for row_index, row in enumerate(grid):
14            for col_index, value in enumerate(row):
15                self.position_map[value] = (row_index, col_index)
16
17    def adjacentSum(self, value: int) -> int:
18        # Calculate the sum of values adjacent to the given value's position
19        return self.calculate_sum(value, 0)
20
21    def diagonalSum(self, value: int) -> int:
22        # Calculate the sum of values diagonally adjacent to the given value's position
23        return self.calculate_sum(value, 1)
24
25    def calculate_sum(self, value: int, direction_type: int) -> int:
26        # Get the current position of the value
27        row, col = self.position_map[value]
28        total_sum = 0
29
30        # Iterate over the pair of directions (for adjacent or diagonal)
31        for a, b in zip(self.directions[direction_type][0], self.directions[direction_type][1]):
32            new_row, new_col = row + a, col + b
33            # Check if the new position is within grid boundaries
34            if 0 <= new_row < len(self.grid) and 0 <= new_col < len(self.grid[0]):
35                total_sum += self.grid[new_row][new_col]
36
37        return total_sum
38
39# Example of how to instantiate and use the NeighborSum class:
40# grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
41# obj = NeighborSum(grid)
42# param_1 = obj.adjacentSum(5)
43# param_2 = obj.diagonalSum(5)
44

1import java.util.HashMap;
2import java.util.Map;
3
4class NeighborSum {
5    private int[][] grid; // The grid representing the 2D matrix
6    private final Map<Integer, int[]> valueToPositionMap = new HashMap<>(); // Map to store the positions of values
7    private final int[][] directions = {{-1, 0, 1, 0, -1}, {-1, 1, 1, -1, -1}}; // Direction vectors
8
9    // Constructor to initialize the grid and populate the map with positions
10    public NeighborSum(int[][] grid) {
11        this.grid = grid;
12        int rows = grid.length;
13        int cols = grid[0].length;
14
15        // Populate the map with each value's position in the grid
16        for (int i = 0; i < rows; ++i) {
17            for (int j = 0; j < cols; ++j) {
18                valueToPositionMap.put(grid[i][j], new int[]{i, j});
19            }
20        }
21    }
22
23    // Calculate the sum of adjacent cells (vertically and horizontally)
24    public int adjacentSum(int value) {
25        return calculateSum(value, 0); // Use '0' to indicate adjacent direction
26    }
27
28    // Calculate the sum of diagonal cells
29    public int diagonalSum(int value) {
30        return calculateSum(value, 1); // Use '1' to indicate diagonal direction
31    }
32
33    // Helper method to calculate sum based on the direction type
34    private int calculateSum(int value, int directionType) {
35        int[] position = valueToPositionMap.get(value); // Get position of the value in the grid
36        int sum = 0;
37
38        // Iterate through the four possible directions
39        for (int index = 0; index < 4; ++index) {
40            int x = position[0] + directions[directionType][index]; // New x coordinate
41            int y = position[1] + directions[directionType][index + 1]; // New y coordinate
42
43            // Check if new coordinates are within grid boundaries
44            if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length) {
45                sum += grid[x][y]; // Add the value at the new coordinates to the sum
46            }
47        }
48        return sum; // Return the calculated sum
49    }
50}
51
52/**
53 * Your NeighborSum object will be instantiated and called as such:
54 * NeighborSum obj = new NeighborSum(grid);
55 * int param_1 = obj.adjacentSum(value);
56 * int param_2 = obj.diagonalSum(value);
57 */
58

1class NeighborSum {
2public:
3    // Constructor to initialize the grid and map each value to its position in the grid.
4    NeighborSum(vector<vector<int>>& grid) {
5        this->grid = grid;
6        int rows = grid.size(), columns = grid[0].size();
7        // Map each grid value to its coordinates (row, column).
8        for (int i = 0; i < rows; ++i) {
9            for (int j = 0; j < columns; ++j) {
10                valueToPosition[grid[i][j]] = {i, j};
11            }
12        }
13    }
14
15    // Method to calculate the sum of adjacent neighbors for the given cell value.
16    int adjacentSum(int value) {
17        return calculate(value, 0);
18    }
19
20    // Method to calculate the sum of diagonal neighbors for the given cell value.
21    int diagonalSum(int value) {
22        return calculate(value, 1);
23    }
24
25private:
26    vector<vector<int>> grid; // 2D grid of integers.
27    unordered_map<int, pair<int, int>> valueToPosition; // Maps grid value to its (row, column) coordinates.
28    int directions[2][5] = {{-1, 0, 1, 0, -1}, {-1, 1, 1, -1, -1}}; // Direction vectors for adjacent and diagonal steps.
29
30    // Helper method to calculate the sum of neighbors based on the mode (adjacent or diagonal).
31    int calculate(int value, int mode) {
32        auto [row, col] = valueToPosition[value]; // Retrieve coordinates of the given value.
33        int sum = 0;
34        // Iterate over the four possible direction steps.
35        for (int step = 0; step < 4; ++step) {
36            int newRow = row + directions[mode][step]; // Compute new row index.
37            int newCol = col + directions[mode][step + 1]; // Compute new column index.
38            // Check if the new position is within grid bounds.
39            if (newRow >= 0 && newRow < grid.size() && newCol >= 0 && newCol < grid[0].size()) {
40                sum += grid[newRow][newCol]; // Add the neighbor's value to the sum.
41            }
42        }
43        return sum; // Return the calculated sum.
44    }
45};
46
47/**
48 * Your NeighborSum object will be instantiated and called as such:
49 * NeighborSum* obj = new NeighborSum(grid);
50 * int param_1 = obj->adjacentSum(value);
51 * int param_2 = obj->diagonalSum(value);
52 */
53

1// Grid which holds the initial matrix input
2let grid: number[][];
3
4// Dictionary to map each value to its position (i, j) in the grid
5let d: Map<number, [number, number]> = new Map();
6
7// Directions for adjacent and diagonal calculations
8const dirs: number[][] = [
9    [-1, 0, 1, 0, -1],  // Directions for adjacent cells (up, right, down, left)
10    [-1, 1, 1, -1, -1], // Directions for diagonal cells (top-left, top-right, bottom-right, bottom-left)
11];
12
13// Initialize grid and map each value to its position
14function initializeGrid(inputGrid: number[][]) {
15    grid = inputGrid;
16    for (let i = 0; i < grid.length; ++i) {
17        for (let j = 0; j < grid[0].length; ++j) {
18            d.set(grid[i][j], [i, j]);
19        }
20    }
21}
22
23// Calculate the sum of adjacent cells for the given value
24function adjacentSum(value: number): number {
25    return cal(value, 0);  // Use 0 as the index for adjacent directions
26}
27
28// Calculate the sum of diagonal cells for the given value
29function diagonalSum(value: number): number {
30    return cal(value, 1);  // Use 1 as the index for diagonal directions
31}
32
33// Generalized function to calculate a sum of surrounding cells
34function cal(value: number, k: number): number {
35    const [i, j] = d.get(value)!;  // Retrieve the position (i, j) for the given value
36    let sum = 0;
37    // Loop through the direction indices
38    for (let q = 0; q < 4; ++q) {
39        // Calculate new positions based on direction
40        const [x, y] = [i + dirs[k][q], j + dirs[k][q + 1]];
41        // Check if new positions are within grid boundaries
42        if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length) {
43            sum += grid[x][y];  // Add value to sum if within bounds
44        }
45    }
46    return sum;
47}
48
49/**
50 * Usage:
51 * initializeGrid(grid)
52 * var param_1 = adjacentSum(value)
53 * var param_2 = diagonalSum(value)
54 */
55

Time and Space Complexity

The time complexity for initializing the hash table, which involves iterating over each element in the grid, is O(m \times n), where m is the number of rows and n is the number of columns.

The adjacentSum and diagonalSum methods both call the cal function. Each call to cal checks a constant number of adjacent or diagonal positions (in this case, four), making their time complexity O(1).

The space complexity is O(m \times n) due to storing the grid and the dictionary d that maps values to their positions.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: