game of life

fishercoder1534 · fishercoder1534 · commit 4f275a56fa63 · 2016-10-31T18:20:53.000-07:00
diff --git a/MEDIUM/src/medium/GameOfLife.java b/MEDIUM/src/medium/GameOfLife.java
@@ -0,0 +1,42 @@
+package medium;
+
+public class GameOfLife {
+    public void gameOfLife(int[][] board) {
+        int height = board.length, width = board[0].length;
+        int[][] next = new int[height][width];
+        
+            for(int i = 0; i < board.length; i++){
+                for(int j = 0; j < board[0].length; j++){
+                        int liveCellsCount = 0;
+                        //count all its live cells
+                        
+                        if(j+1 < width && board[i][j+1] == 1) liveCellsCount++;//right cell
+                        if(j-1 >= 0 && board[i][j-1] == 1) liveCellsCount++;//left cell
+                        if(i+1 < height && board[i+1][j] == 1) liveCellsCount++;//down cell
+                        if(i-1 >= 0 && board[i-1][j] == 1) liveCellsCount++;//up cell
+                        if(i-1 >= 0 && j-1 >= 0 && board[i-1][j-1] == 1) liveCellsCount++;//up left cell
+                        if(i-1 >= 0 && j+1 < width && board[i-1][j+1] == 1) liveCellsCount++;//up right cell
+                        if(i+1 < height && j-1 >= 0 && board[i+1][j-1] == 1) liveCellsCount++;//down left cell
+                        if(i+1 < height && j+1 < width && board[i+1][j+1] == 1) liveCellsCount++;//down right cell
+                        
+                        if(board[i][j] == 1){
+                            if(liveCellsCount > 3 || liveCellsCount < 2) {
+                                next[i][j] = 0;
+                            } else {
+                                next[i][j] = 1;
+                            }
+                        } else if(board[i][j] == 0) {
+                            if(liveCellsCount == 3){
+                                next[i][j] = 1;
+                            }
+                        } 
+                }
+            }
+            
+            for(int i = 0; i < board.length; i++){
+                for(int j = 0; j < board[0].length; j++){
+                    board[i][j] = next[i][j];
+                }
+            }
+    }
+}
diff --git a/README.md b/README.md
@@ -22,6 +22,7 @@
 |301|[Remove Invalid Parentheses](https://leetcode.com/problems/remove-invalid-parentheses/)|[Solution]| ? | ? | Hard| BFS
 |299|[Bulls and Cows](https://leetcode.com/problems/bulls-and-cows/)|[Solution](../../blob/master/EASY/src/easy/BullsandCows.java)| O(n)|O(1) | Easy| 
 |292|[Nim Game](https://leetcode.com/problems/nim-game/)|[Solution](../../blob/master/EASY/src/easy/NimGame.java)| O(1)|O(1) | Easy| 
+|289|[Game of Life](https://leetcode.com/problems/game-of-life/)|[Solution](../../blob/master/MEDIUM/src/medium/GameOfLife.java)| O(m*n)|O(m*n), could be optimized to O(1) | Medium|
 |283|[Move Zeroes](https://leetcode.com/problems/move-zeroes/)|[Solution](../../blob/master/EASY/src/easy/MoveZeroes.java)| O(n)|O(1) | Easy| 
 |280|[Wiggle Sort](https://leetcode.com/problems/wiggle-sort/)|[Solution](../../blob/master/MEDIUM/src/medium/WiggleSort.java)| O(n)|O(1) | Medium|
 |278|[First Bad Version](https://leetcode.com/problems/first-bad-version/)|[Solution](../../blob/master/EASY/src/easy/FirstBadVersion.java)| O(logn)|O(1) | Easy| Binary Search
