1
/**
2
 * @param {number[][]} grid
3
 * @param {number} stampHeight
4
 * @param {number} stampWidth
5
 * @return {boolean}
6
 */
7
var possibleToStamp = function (grid, stampHeight, stampWidth) {
8
  const w = grid[0].length;
9
  const h = grid.length;
10

11
  // dp[i + 1][j + 1] - sum of cells in the rectangle, where
12
  // (0, 0) is the left upper corner in the matrix,
13
  // (i, j) is the rigth down corner in the matrix
14
  function getSumOfRectangle(matrix) {
15
    const h = matrix.length;
16
    const w = matrix[0].length;
17
    const dp = new Array(h + 1);
18
    dp[0] = new Array(w + 1).fill(0);
19
    for (let i = 0; i < h; i++) {
20
      dp[i + 1] = new Array(w + 1);
21
      dp[i + 1][0] = 0;
22
      for (let j = 0; j < w; j++) {
23
        dp[i + 1][j + 1] =
24
          dp[i + 1][j] + dp[i][j + 1] - dp[i][j] + matrix[i][j];
25
      }
26
    }
27
    return dp;
28
  }
29

30
  const dp = getSumOfRectangle(grid);
31

32
  // diff[i][j] === 1 <- start of the stamp (its left upper corner is in point (i, j))
33
  // diff[i][j] === -1 <- a border of the stamp
34
  // (its corner is either (i, j - 1) or (i - 1, j) or (i - 1, j - 1))
35
  const diff = new Array(h + 1);
36

37
  // 1) fill diff with zeros
38
  for (let i = 0; i <= h; i++) {
39
    diff[i] = new Array(w + 1).fill(0);
40
  }
41

42
  for (let i = 0; i <= h - stampHeight; i++) {
43
    for (let j = 0; j <= w - stampWidth; j++) {
44
      // isFitPossible === 0 <- we can put the stamp,
45
      // such that its left upper corner is in point (i, j)
46
      // isFitPossible > 0 <- we can't put the stamp,
47
      // such that its left upper corner is in point (i, j)
48
      const isFitPossible =
49
        dp[i + stampHeight][j + stampWidth] -
50
        dp[i + stampHeight][j] -
51
        dp[i][j + stampWidth] +
52
        dp[i][j];
53

54
      if (isFitPossible === 0) {
55
        diff[i][j] += 1;
56
        diff[i][j + stampWidth] += -1;
57
        diff[i + stampHeight][j] += -1;
58
        diff[i + stampHeight][j + stampWidth] += 1;
59
      }
60
    }
61
  }
62

63
  const dp2 = getSumOfRectangle(diff);
64
  for (let i = 0; i < h; i++) {
65
    for (let j = 0; j < w; j++) {
66
      if (dp2[i + 1][j + 1] === 0 && grid[i][j] != 1) {
67
        return false;
68
      }
69
    }
70
  }
71
  return true;
72
};