22 Sept 2023•TypeScript•Medium

Design Neighbor Sum Service

design a service to compute sums of adjacent and diagonal neighbors using prefix sums and linear search.

build a prefix sum during construction for efficient range queries (though not strictly needed here). for neighbor sums, find the target value's position, then sum its four adjacent or four diagonal neighbors with bounds checking.

the key is safe access: check bounds before accessing grid cells to handle edge cases where neighbors might be out of bounds.

methods

adjacentSum: sum of up, down, left, right neighbors
diagonalSum: sum of four diagonal neighbors
both use safeGet to handle out-of-bounds gracefully

complexity

O(mn) time to find target value, O(1) for neighbor sums. O(mn) space for grid and prefix arrays.

Solution files

TypeScript•design-neighbor-sum-service/solution.ts

class NeighborSum {
  private readonly grid: number[][];
  private readonly prefix: number[][];

  constructor(grid: number[][]) {
    this.grid = grid;
    this.prefix = this.buildPrefix(grid);
  }

  adjacentSum(value: number): number {
    const [r, c] = this.find(value);
    if (r === -class="syntax-number">1) {
      return class="syntax-number">0;
    }

    let total = class="syntax-number">0;
    total += this.safeGet(r - class="syntax-number">1, c);
    total += this.safeGet(r + class="syntax-number">1, c);
    total += this.safeGet(r, c - class="syntax-number">1);
    total += this.safeGet(r, c + class="syntax-number">1);
    return total;
  }

  diagonalSum(value: number): number {
    const [r, c] = this.find(value);
    if (r === -class="syntax-number">1) {
      return class="syntax-number">0;
    }

    let total = class="syntax-number">0;
    total += this.safeGet(r - class="syntax-number">1, c - class="syntax-number">1);
    total += this.safeGet(r - class="syntax-number">1, c + class="syntax-number">1);
    total += this.safeGet(r + class="syntax-number">1, c - class="syntax-number">1);
    total += this.safeGet(r + class="syntax-number">1, c + class="syntax-number">1);
    return total;
  }

  private buildPrefix(grid: number[][]): number[][] {
    const rows = grid.length;
    const cols = rows ? grid[class="syntax-number">0].length : class="syntax-number">0;
    const prefix = Array.from({ length: rows + class="syntax-number">1 }, () =>
      new Array<number>(cols + class="syntax-number">1).fill(class="syntax-number">0),
    );

    for (let r = class="syntax-number">0; r < rows; ++r) {
      for (let c = class="syntax-number">0; c < cols; ++c) {
        prefix[r + class="syntax-number">1][c + class="syntax-number">1] =
          grid[r][c] + prefix[r][c + class="syntax-number">1] + prefix[r + class="syntax-number">1][c] - prefix[r][c];
      }
    }

    return prefix;
  }

  private find(target: number): [number, number] {
    for (let r = class="syntax-number">0; r < this.grid.length; ++r) {
      for (let c = class="syntax-number">0; c < this.grid[r].length; ++c) {
        if (this.grid[r][c] === target) {
          return [r, c];
        }
      }
    }
    return [-class="syntax-number">1, -class="syntax-number">1];
  }

  private safeGet(r: number, c: number): number {
    if (r < class="syntax-number">0 || c < class="syntax-number">0 || r >= this.grid.length || c >= this.grid[class="syntax-number">0].length) {
      return class="syntax-number">0;
    }
    return this.grid[r][c];
  }
}

export { NeighborSum };