Array-2/GameOfLife.java at a73455ec9fd47936289c73b34ce4006a916b4a50 · super30admin/Array-2 · 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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
// O(n * m) time, O(n * m) space
// class Solution {
//     public void gameOfLife(int[][] board) {
//         int n = board.length;
//         int m = board[0].length;
//         int[][] copy = new int[n][m];

//         int[][] dirs = new int[][] {
//             {0,1},
//             {0,-1},
//             {1,0},
//             {-1,0},
//             {1,1},
//             {-1,1},
//             {1,-1},
//             {-1,-1}
//         };

//         for (int i = 0; i < n; i++) {
//             for (int j = 0; j < m; j++) {
//                 copy[i][j] = board[i][j];
//             }
//         }

//         for (int i = 0; i < n; i++) {
//             for (int j = 0; j < m; j++) {
//                 int cell = board[i][j];
//                 int live = getLiveNeighbors(i, j, board, dirs);

//                 if (cell == 1 && (live < 2 || live > 3)) {
//                     copy[i][j] = 0;
//                 }
//                 else if (cell == 1 && (live == 2 || live == 3)) {
//                     copy[i][j] = 1;
//                 }
//                 else if (cell == 0 && live == 3) {
//                     copy[i][j] = 1;
//                 }
//                 else {
//                     copy[i][j] = 0;
//                 }
//             }
//         }

//         for (int i = 0; i < n; i++) {
//             for (int j = 0; j < m; j++) {
//                 board[i][j] = copy[i][j];
//             }
//         }
//     }

//     private int getLiveNeighbors(int i, int j, int[][] board, int[][] dirs) {
//         int n = board.length;
//         int m = board[0].length;

//         int liveCellCount = 0;

//         for (int[] dir : dirs) {
//             int newI = i + dir[0];
//             int newJ = j + dir[1];

//             if (newI >= 0 && newJ >= 0 && newI < n && newJ < m) {
//                 if (board[newI][newJ] == 1) {
//                     liveCellCount++;
//                 }
//             }
//         }
//         return liveCellCount;
//     }
// }

// O(n * m) time, O(1) space
class Solution {
    public void gameOfLife(int[][] board) {
        int n = board.length;
        int m = board[0].length;

        int[][] dirs = new int[][] {
            {0,1},
            {0,-1},
            {1,0},
            {-1,0},
            {1,1},
            {-1,1},
            {1,-1},
            {-1,-1}
        };

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int cell = board[i][j];
                int live = getLiveNeighbors(i, j, board, dirs);

                if (cell == 1 && (live < 2 || live > 3)) {
                    board[i][j] = 5; // was alive now dead, alive -> dead
                }
                else if (cell == 1 && (live == 2 || live == 3)) {
                    board[i][j] = 1;
                }
                else if (cell == 0 && live == 3) {
                    board[i][j] = 10; // was dead now alive, dead -> alive
                }
                else {
                    board[i][j] = 0;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 5) { // alive -> dead so now mark dead
                    board[i][j] = 0;
                }
                else if (board[i][j] == 10) { // dead -> alive so now mark alive
                    board[i][j] = 1;
                }
            }
        }
    }

    private int getLiveNeighbors(int i, int j, int[][] board, int[][] dirs) {
        int n = board.length;
        int m = board[0].length;

        int liveCellCount = 0;

        for (int[] dir : dirs) {
            int newI = i + dir[0];
            int newJ = j + dir[1];

            if (newI >= 0 && newJ >= 0 && newI < n && newJ < m) {
                if (board[newI][newJ] == 1 || board[newI][newJ] == 5) {
                    liveCellCount++;
                }
            }
        }
        return liveCellCount;
    }
}