3242. Design Neighbor Sum Service LeetCode Solution
In this guide, you will get 3242. Design Neighbor Sum Service LeetCode Solution with the best time and space complexity. The solution to Design Neighbor Sum Service problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
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] <= n2 – 1
All grid[i][j] are distinct.
value in adjacentSum and diagonalSum will be in the range [0, n2 – 1].
At most 2 * n2 calls will be made to adjacentSum and diagonalSum.
Complexity Analysis
Time Complexity: O(1)
Space Complexity: O(mn)
3242. Design Neighbor Sum Service LeetCode Solution in C++
class neighborSum {
public:
neighborSum(vector<vector<int>>& grid)
: n(grid.size()), grid(grid), numToPos(n * n) {
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
numToPos[grid[i][j]] = {i, j};
}
int adjacentSum(int value) {
const auto& [i, j] = numToPos[value];
int sum = 0;
for (const auto& [x, y] :
vector<pair<int, int>>{{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}})
if (x >= 0 && x < n && y >= 0 && y < n)
sum += grid[x][y];
return sum;
}
int diagonalSum(int value) {
const auto& [i, j] = numToPos[value];
int sum = 0;
for (const auto& [x, y] : vector<pair<int, int>>{
{i - 1, j - 1}, {i - 1, j + 1}, {i + 1, j - 1}, {i + 1, j + 1}})
if (x >= 0 && x < n && y >= 0 && y < n)
sum += grid[x][y];
return sum;
}
private:
const int n;
vector<vector<int>> grid;
vector<pair<int, int>> numToPos;
}; /* code provided by PROGIEZ */
3242. Design Neighbor Sum Service LeetCode Solution in Java
class neighborSum {
public neighborSum(int[][] grid) {
this.n = grid.length;
this.grid = grid;
this.numToPos = new Pair[n * n];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
numToPos[grid[i][j]] = new Pair<>(i, j);
}
public int adjacentSum(int value) {
final int i = numToPos[value].getKey();
final int j = numToPos[value].getValue();
int sum = 0;
int[][] directions = {{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}};
for (int[] dir : directions) {
final int x = dir[0];
final int y = dir[1];
if (x >= 0 && x < n && y >= 0 && y < n)
sum += grid[x][y];
}
return sum;
}
public int diagonalSum(int value) {
final int i = numToPos[value].getKey();
final int j = numToPos[value].getValue();
int sum = 0;
int[][] directions = {{i - 1, j - 1}, {i - 1, j + 1}, {i + 1, j - 1}, {i + 1, j + 1}};
for (int[] dir : directions) {
final int x = dir[0];
final int y = dir[1];
if (x >= 0 && x < n && y >= 0 && y < n)
sum += grid[x][y];
}
return sum;
}
private int n;
private int[][] grid;
private Pair<Integer, Integer>[] numToPos;
} // code provided by PROGIEZ
3242. Design Neighbor Sum Service LeetCode Solution in Python
class neighborSum:
def __init__(self, grid: list[list[int]]):
self.grid = grid
self.n = len(grid)
self.numToPos = {num: (i, j)
for i, row in enumerate(grid)
for j, num in enumerate(row)}
def adjacentSum(self, value: int) -> int:
i, j = self.numToPos[value]
return sum(self.grid[x][y]
for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1))
if 0 <= x < self.n and 0 <= y < self.n)
def diagonalSum(self, value: int) -> int:
i, j = self.numToPos[value]
return sum(self.grid[x][y]
for x, y in ((i - 1, j - 1), (i - 1, j + 1),
(i + 1, j - 1), (i + 1, j + 1))
if 0 <= x < self.n and 0 <= y < self.n) # code by PROGIEZ
