Design Neighbor Sum Service
EasyArrayHash TableDesignMatrixSimulation
Solution
export class NeighborSum {
readonly n: number;
readonly grid: number[][];
private readonly adjecentSums: number[];
private readonly diagonalSums: number[];
constructor(grid: number[][]) {
this.n = grid.length;
this.grid = grid;
this.adjecentSums = new Array(this.n ** 2).fill(0);
this.diagonalSums = new Array(this.n ** 2).fill(0);
this.initSums();
}
private initSums() {
const adjecents = [0, 1, 0, -1, 0];
const diagonals = [1, 1, -1, -1, 1];
for (let y = 0; y < this.n; y++) {
for (let x = 0; x < this.n; x++) {
for (let i = 0; i < 4; i++) {
const [ay, ax] = [adjecents[i], adjecents[i + 1]];
this.addSums(this.adjecentSums, y + ay, x + ax, this.grid[y][x]);
const [dy, dx] = [diagonals[i], diagonals[i + 1]];
this.addSums(this.diagonalSums, y + dy, x + dx, this.grid[y][x]);
}
}
}
}
private addSums(sums: number[], y: number, x: number, value: number) {
if (Math.min(y, x) < 0 || Math.max(y, x) >= this.n) {
return;
}
sums[value] += this.grid[y][x];
}
adjacentSum(value: number): number {
return this.adjecentSums[value];
}
diagonalSum(value: number): number {
return this.diagonalSums[value];
}
}
Complexity
- Time:
O(N^2)
- Space:
O(N^2)