Skip to content

3242. Design Neighbor Sum Service 👍

  • Time:
    • Constructor: $O(mn)$
    • adjacentSum(value: int): $O(1)$
    • diagonalSum(value: int): $O(1)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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)