Sponsored
Sponsored
This approach creates a copy of the original board. It calculates the new state for each cell using the current state from the original board while updating the new state in the copy. Once all cells have been processed, it updates the original board with the calculated states from the copy.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns, because each cell is visited once.
Space Complexity: O(m * n), due to the additional copy of the board.
1#include <stdio.h>
2#include <stdlib.h>
3
4void gameOfLife(int** board, int boardSize, int* boardColSize) {
5 int m = boardSize;
6 int n = *boardColSize;
7
8 // Copy of the board
9 int** copy = (int**)malloc(m * sizeof(int*));
10 for (int i = 0; i < m; i++) {
11 copy[i] = (int*)malloc(n * sizeof(int));
12 for (int j = 0; j < n; j++) {
13 copy[i][j] = board[i][j];
14 }
15 }
16
17 // Directions for neighbors
18 int directions[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
19
20 for (int i = 0; i < m; i++) {
21 for (int j = 0; j < n; j++) {
22 int liveNeighbors = 0;
23 for (int d = 0; d < 8; d++) {
24 int ni = i + directions[d][0];
25 int nj = j + directions[d][1];
26 if (ni >= 0 && ni < m && nj >= 0 && nj < n && copy[ni][nj] == 1) {
27 liveNeighbors++;
28 }
29 }
30
31 if (copy[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
32 board[i][j] = 0;
33 } else if (copy[i][j] == 0 && liveNeighbors == 3) {
34 board[i][j] = 1;
35 }
36 }
37 }
38
39 for (int i = 0; i < m; i++) {
40 free(copy[i]);
41 }
42 free(copy);
43}
44This C solution uses an additional matrix to store the new state of each cell while retaining the current state in the original matrix. For each cell, its live neighbors are counted, and rules are applied to determine its next state. Once every cell's state is determined, the original board is updated. Memory is dynamically allocated for the copy and freed after use.
This approach uses in-place updates by leveraging different state values. We introduce temporary states: 2 represents a cell that was originally live (1) but will be dead in the next state, and -1 represents a cell that was dead (0) but will be live in the next state. At the end, these temporary states are converted to the final states.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(1), as no additional space is used beyond input storage.
1
The C solution uses the board itself to track changes by representing transitional states so the board can be accurately updated in one iteration by determining the final state in a second pass.