leetcode-javascript/solutions/0723-candy-crush.js at development · Anuj9826/leetcode-javascript · GitHub

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/**
 * Candy Crush
 * Time Complexity: O((M * N)^2)
 * Space Complexity: O(1)
 */
var candyCrush = function (board) {
  const boardRowCount = board.length;
  const boardColCount = board[0].length;

  while (performCrushAndMark()) {
    applyGravitySimulation();
  }

  return board;

  function performCrushAndMark() {
    let crushablesFound = false;

    for (
      let currentRowIndex = 0;
      currentRowIndex < boardRowCount;
      currentRowIndex++
    ) {
      for (
        let currentColIndex = 0;
        currentColIndex < boardColCount - 2;
        currentColIndex++
      ) {
        const horizontalCandyType = Math.abs(
          board[currentRowIndex][currentColIndex],
        );
        if (
          horizontalCandyType !== 0 &&
          horizontalCandyType ===
            Math.abs(board[currentRowIndex][currentColIndex + 1]) &&
          horizontalCandyType ===
            Math.abs(board[currentRowIndex][currentColIndex + 2])
        ) {
          crushablesFound = true;
          board[currentRowIndex][currentColIndex] = -horizontalCandyType;
          board[currentRowIndex][currentColIndex + 1] = -horizontalCandyType;
          board[currentRowIndex][currentColIndex + 2] = -horizontalCandyType;
        }
      }
    }

    for (
      let currentColumnIndex = 0;
      currentColumnIndex < boardColCount;
      currentColumnIndex++
    ) {
      for (
        let currentVerticalRowIndex = 0;
        currentVerticalRowIndex < boardRowCount - 2;
        currentVerticalRowIndex++
      ) {
        const verticalCandyType = Math.abs(
          board[currentVerticalRowIndex][currentColumnIndex],
        );
        if (
          verticalCandyType !== 0 &&
          verticalCandyType ===
            Math.abs(board[currentVerticalRowIndex + 1][currentColumnIndex]) &&
          verticalCandyType ===
            Math.abs(board[currentVerticalRowIndex + 2][currentColumnIndex])
        ) {
          crushablesFound = true;
          board[currentVerticalRowIndex][currentColumnIndex] =
            -verticalCandyType;
          board[currentVerticalRowIndex + 1][currentColumnIndex] =
            -verticalCandyType;
          board[currentVerticalRowIndex + 2][currentColumnIndex] =
            -verticalCandyType;
        }
      }
    }

    return crushablesFound;
  }

  function applyGravitySimulation() {
    for (
      let columnIterator = 0;
      columnIterator < boardColCount;
      columnIterator++
    ) {
      let writeTargetRow = boardRowCount - 1;
      for (
        let readSourceRow = boardRowCount - 1;
        readSourceRow >= 0;
        readSourceRow--
      ) {
        if (board[readSourceRow][columnIterator] > 0) {
          board[writeTargetRow][columnIterator] =
            board[readSourceRow][columnIterator];
          if (writeTargetRow !== readSourceRow) {
            board[readSourceRow][columnIterator] = 0;
          }
          writeTargetRow--;
        } else if (board[readSourceRow][columnIterator] < 0) {
          board[readSourceRow][columnIterator] = 0;
        }
      }
    }
  }
};