algoadvance

Leetcode 3242. Design Neighbor Sum Service

Problem Statement

Design a service that provides the sum of all neighbors of a given cell in a 2D grid. The 2D grid will be updated frequently, and for each update, you should be able to quickly recalculate the sum of neighbors for any given cell.

Implement the NeighborSumService class:

• NeighborSumService(int[][] grid) Initializes the object with the given 2D grid.
• void update(int row, int col, int val) Updates the value at the given cell (row, col) to val.
• int sum_neighbors(int row, int col) Returns the sum of all 8 neighbors of the cell (row, col). If a neighbor is out of bounds, it should not be included in the sum.

Clarifying Questions

1. What are the dimensions of the grid?
   • The dimensions are provided in the grid during the initialization and could vary for each grid.
2. What is the expected range of row and column indices?
   • The indices for row and column will always be within the bounds of the grid.
3. What should be done if the indices for update or sum_neighbors method are out of bounds?
   • You can assume valid inputs; there’s no need for bounds checking in your methods.
4. Is the grid immutable after initialization apart from the explicit updates through the update method?
   • Yes, the grid will only change through the update method.

Strategy

1. Initialization: Store the initial grid.
2. Update: For the update operation, change the grid at the specified position.
3. Sum Calculation: For each cell, check its eight possible neighbors, and sum their values if they are within bounds.

Code

#include <vector>
using namespace std;

class NeighborSumService {
public:
    NeighborSumService(vector<vector<int>>& grid) : grid(grid) {}
    
    void update(int row, int col, int val) {
        grid[row][col] = val;
    }
    
    int sum_neighbors(int row, int col) {
        int sum = 0;
        vector<pair<int, int>> directions = \{\{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        for (auto [dx, dy] : directions) {
            int newRow = row + dx;
            int newCol = col + dy;
            if (newRow >= 0 && newRow < grid.size() && newCol >= 0 && newCol < grid[0].size()) {
                sum += grid[newRow][newCol];
            }
        }
        return sum;
    }

private:
    vector<vector<int>> grid;
};

Time Complexity

• Initialization: O(1) since only storing the reference to the grid.
• Update: O(1) since it directly updates the value at a specific location.
• Sum Calculation: O(1) as it always checks a fixed number (eight) of neighboring cells.

Explanation

1. Initialization:
   • The grid is stored directly during object creation.
2. Update Method:
   • The value at the given position (row, col) in the grid is updated to val.
3. Sum Calculation Method:
   • Iterate over all possible directions to calculate the sum of the neighbors.
   • Using a list of possible directions vectors to facilitate checking the neighbors.
   • Check boundaries before adding the neighbor’s value to ensure it’s within the grid.

This setup ensures that updates and neighbor sum calculations are efficient, making the service responsive for frequent operations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?