Prison Cells After N Days solution and explanation
9 more videos on this problem
Prison Cells After N Days | Leetcode #957Techdose · 18:01 · 14K views
Prison Cells After N Days | LeetCode 957 | C++, Java, PythonKnowledge Center · 29:03 · 6K views
Prison Cells After N Days | prison cells after n days | prison cells after n days leetcodeAkshay Goyal · 10:06 · 4K views
LeetCode 957. Prison Cells After N Days - Interview Prep Ep 81Fisher Coder · 15:34 · 3K views
Prison Cells After N Days | leetcode 957 | HindiCodebix · 16:37 · 3K views
prison cells after n days | prison cells after n days leetcode | leetcode 957Naresh Gupta · 14:36 · 2K views
Leetcode - Prison Cells After N Days (Python)Timothy H Chang · 6:29 · 2K views
Prison Cells After N Days | Leet code 957 | Theory explained + Python code | July code challengeSai Anish Malla · 14:26 · 1K views
Coding Interview Problem - Prison Cells After N DaysKnapsack · 8:58 · 1K views
Daily Leetcode #94: Jul 03, 2020 - 957. Prison Cells After N DaysProgramming Live with Larry · 24:07 · 673 views
The problem
There are 8 prison cells in a row and each cell is either occupied or vacant.
Each day, whether the cell is occupied or vacant changes according to the following rules:
- If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
- Otherwise, it becomes vacant.
Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors.
You are given an integer array cells where cells[i] == 1 if the ith cell is occupied and cells[i] == 0 if the ith cell is vacant, and you are given an integer n.
Return the state of the prison after n days (i.e., n such changes described above).
Example 1:
Input: cells = [0,1,0,1,1,0,0,1], n = 7 Output: [0,0,1,1,0,0,0,0] Explanation: The following table summarizes the state of the prison on each day: Day 0: [0, 1, 0, 1, 1, 0, 0, 1] Day 1: [0, 1, 1, 0, 0, 0, 0, 0] Day 2: [0, 0, 0, 0, 1, 1, 1, 0] Day 3: [0, 1, 1, 0, 0, 1, 0, 0] Day 4: [0, 0, 0, 0, 0, 1, 0, 0] Day 5: [0, 1, 1, 1, 0, 1, 0, 0] Day 6: [0, 0, 1, 0, 1, 1, 0, 0] Day 7: [0, 0, 1, 1, 0, 0, 0, 0]
Example 2:
Input: cells = [1,0,0,1,0,0,1,0], n = 1000000000 Output: [0,0,1,1,1,1,1,0]
Constraints:
cells.length == 8cells[i]is either0or1.1 <= n <= 109
Approach overview
Problem Overview: You are given 8 prison cells arranged in a row where each cell is either occupied (1) or vacant (0). Every day the state changes: a cell becomes occupied if its two neighbors were both occupied or both empty the previous day; otherwise it becomes vacant. The first and last cells always become 0 because they have only one neighbor. Given an initial configuration and an integer N, compute the state after N days.
Approach 1: Simulate Each Day (Time: O(N * 8), Space: O(8))
The direct approach is to simulate the transformation day by day. For each day, create a new array and iterate through indices 1..6. A cell becomes 1 when cells[i-1] == cells[i+1], otherwise 0. The edge cells are always set to 0. Since there are only 8 cells, each day's computation takes constant time, so the total complexity is O(N). This approach is simple and useful when N is small, but it becomes impractical when N can reach values like 10^9.
Approach 2: Identify Cycle in States (Time: O(min(N, cycle)) ≈ O(1), Space: O(2^6))
The key observation is that the system eventually repeats. The first and last cells are always 0 after the first day, so only the 6 middle cells change. That means there are at most 2^6 = 64 possible states. If you store each configuration in a hash table, you can detect when a state repeats. Once a cycle is found, reduce N using N % cycle_length and simulate only the remaining days. This turns a potentially huge simulation into a small constant number of steps. Many implementations encode the state as a bitmask using bit manipulation, which makes transitions fast and compact. The grid itself is handled as an array, while the hash table tracks previously seen states.
Recommended for interviews: Start by describing the daily simulation to show you understand the rule transition. Then point out that only 6 cells vary, giving at most 64 possible states. Recognizing this repetition and applying cycle detection with a hash map is the expected optimized solution. Interviewers typically want the cycle insight because it handles extremely large N efficiently.
Approach 1: Simulate Each Day
This approach involves simulating each day's changes directly. Given the constraints of the problem, this can be manageable for relatively small values of 'n'. We iterate over each day, applying the rules to determine the state of each cell. Importantly, the edge cells are always vacant as they lack two neighbors. By updating the state iteratively, we can reach the final configuration after 'n' days.
def next_day(cells):
return [0] + [cells[i - 1] == cells[i + 1] for i in range(1, 7)] + [0]
def prison_after_n_days(cells, N):
N = N % 14 if N % 14 != 0 else 14 # Cycle found of length 14
for _ in range(N):
cells = next_day(cells)
return cells
# Example usage
cells = [0, 1, 0, 1, 1, 0, 0, 1]
N = 7
result = prison_after_n_days(cells, N)
print(result)import java.util.Arrays;
public class PrisonCells {
public static int[] nextDay(int[] cells) {
int[] nextCells = new int[8];
for (int i = 1; i < 7; ++i) {
nextCells[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
}
return nextCells;
}
public static int[] prisonAfterNDays(int[] cells, int N) {
N = N % 14 == 0 ? 14 : N % 14; // Reduce by cycle length
for (int i = 0; i < N; ++i) {
cells = nextDay(cells);
}
return cells;
}
public static void main(String[] args) {
int[] cells = {0, 1, 0, 1, 1, 0, 0, 1};
int N = 7;
int[] result = prisonAfterNDays(cells, N);
System.out.println(Arrays.toString(result));
}
}#include <vector>
#include <iostream>
std::vector<int> nextDay(const std::vector<int> &cells) {
std::vector<int> nextCells(8, 0);
for (int i = 1; i < 7; ++i) {
nextCells[i] = cells[i - 1] == cells[i + 1];
}
return nextCells;
}
std::vector<int> prisonAfterNDays(std::vector<int> cells, int n) {
n = n % 14 == 0 ? 14 : n % 14; // Handle periodicity
for (int i = 0; i < n; ++i) {
cells = nextDay(cells);
}
return cells;
}
int main() {
std::vector<int> cells = {0, 1, 0, 1, 1, 0, 0, 1};
int n = 7;
std::vector<int> result = prisonAfterNDays(cells, n);
for (int cell : result) {
std::cout << cell << " ";
}
return 0;
}function nextDay(cells) {
const nextCells = Array(8).fill(0);
for (let i = 1; i < 7; i++) {
nextCells[i] = cells[i - 1] === cells[i + 1] ? 1 : 0;
}
return nextCells;
}
function prisonAfterNDays(cells, N) {
N = N % 14 === 0 ? 14 : N % 14; // Cycle detection
for (let i = 0; i < N; i++) {
cells = nextDay(cells);
}
return cells;
}
// Example usage
const cells = [0, 1, 0, 1, 1, 0, 0, 1];
const N = 7;
console.log(prisonAfterNDays(cells, N));#include <stdio.h>
#include <string.h>
void nextDay(int *cells, int *nextCells) {
nextCells[0] = 0;
nextCells[7] = 0;
for (int i = 1; i < 7; ++i) {
nextCells[i] = cells[i - 1] == cells[i + 1];
}
}
void prisonAfterNDays(int *cells, int n, int *result) {
int nextCells[8];
n = n % 14 == 0 ? 14 : n % 14; // Optimization purpose
for (int i = 0; i < n; ++i) {
nextDay(cells, nextCells);
memcpy(cells, nextCells, 8 * sizeof(int));
}
memcpy(result, cells, 8 * sizeof(int));
}
int main() {
int cells[8] = {0, 1, 0, 1, 1, 0, 0, 1};
int n = 7;
int result[8];
prisonAfterNDays(cells, n, result);
for(int i = 0; i < 8; i++) {
printf("%d ", result[i]);
}
return 0;
}using System;
public class PrisonCells {
public static int[] NextDay(int[] cells) {
int[] nextCells = new int[8];
for (int i = 1; i < 7; ++i) {
nextCells[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
}
return nextCells;
}
public static int[] PrisonAfterNDays(int[] cells, int N) {
N = N % 14 == 0 ? 14 : N % 14; // Optimize for large N
for (int i = 0; i < N; ++i) {
cells = NextDay(cells);
}
return cells;
}
public static void Main(string[] args) {
int[] cells = new int[] {0, 1, 0, 1, 1, 0, 0, 1};
int N = 7;
int[] result = PrisonAfterNDays(cells, N);
Console.WriteLine(string.Join(", ", result));
}
}The Python example demonstrates a concise approach using list comprehensions for daily state changes, with next_day computing the next configuration of cells. The state transition is optimized by observing cyclic behavior, ensuring that it only processes the minimum necessary iterations.
Time complexity: O(1). Limited to cycle evaluation.
Space complexity: O(1). The array size remains constant throughout.
Approach 2: Identify Cycle in States
This alternative approach builds on recognizing patterns within the transformations. Given only 8 cells and binary states, the maximum number of possible unique states is 27 = 128. Through simulation, we can identify that the pattern cycles or repeats after at most 14 days, reducing the need to simulate all given 'n' days. By finding cycles, one can compute the state that would correspond to the final day directly, drastically minimizing operations.
def cells_to_string(cells):
return ''.join(map(str, cells))
def prison_after_n_days(cells, N):
seen = {}
cycle = 0
while N > 0:
cells_str = cells_to_string(cells)
if cells_str in seen:
N %= cycle - seen[cells_str]
seen[cells_str] = cycle
if N > 0:
N -= 1
cells = [0] + [int(cells[i - 1] == cells[i + 1]) for i in range(1, 7)] + [0]
cycle += 1
return cells
# Example usage
cells = [0, 1, 0, 1, 1, 0, 0, 1]
N = 7
result = prison_after_n_days(cells, N)
print(result)import java.util.HashMap;
import java.util.Map;
public class PrisonCells {
public static String cellsToString(int[] cells) {
StringBuilder result = new StringBuilder();
for (int cell : cells) {
result.append(cell);
}
return result.toString();
}
public static int[] prisonAfterNDays(int[] cells, int N) {
Map<String, Integer> seen = new HashMap<>();
int cycle = 0;
while (N > 0) {
String cellState = cellsToString(cells);
if (seen.containsKey(cellState)) {
N %= cycle - seen.get(cellState);
}
seen.put(cellState, cycle);
if (N > 0) {
N--;
int[] next = new int[8];
for (int i = 1; i < 7; ++i) {
next[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
}
cells = next;
cycle++;
}
}
return cells;
}
public static void main(String[] args) {
int[] cells = {0, 1, 0, 1, 1, 0, 0, 1};
int N = 7;
int[] result = prisonAfterNDays(cells, N);
for (int cell : result) {
System.out.print(cell + " ");
}
}
}#include <vector>
#include <unordered_map>
#include <string>
#include <iostream>
std::string cellsToString(const std::vector<int> &cells) {
std::string result;
for (int cell : cells) {
result += std::to_string(cell);
}
return result;
}
std::vector<int> prisonAfterNDays(std::vector<int> cells, int n) {
std::unordered_map<std::string, int> seen;
int cycle = 0;
while (n > 0) {
std::string cellsStr = cellsToString(cells);
if (seen.find(cellsStr) != seen.end()) {
n %= cycle - seen[cellsStr];
}
seen[cellsStr] = cycle;
if (n > 0) {
--n;
std::vector<int> next(8, 0);
for (int i = 1; i < 7; ++i) {
next[i] = cells[i - 1] == cells[i + 1];
}
cells = next;
++cycle;
}
}
return cells;
}
int main() {
std::vector<int> cells = {0, 1, 0, 1, 1, 0, 0, 1};
int n = 7;
std::vector<int> result = prisonAfterNDays(cells, n);
for (int cell : result) {
std::cout << cell << " ";
}
return 0;
}function cellsToString(cells) {
return cells.join('');
}
function prisonAfterNDays(cells, N) {
let seen = {}, cycle = 0;
while (N > 0) {
let cellsStr = cellsToString(cells);
if (cellsStr in seen) {
N %= cycle - seen[cellsStr];
}
seen[cellsStr] = cycle;
if (N > 0) {
N--;
let next = new Array(8);
for (let i = 1; i < 7; i++) {
next[i] = cells[i - 1] === cells[i + 1] ? 1 : 0;
}
next[0] = next[7] = 0;
cells = next;
cycle++;
}
}
return cells;
}
// Example usage
const cells = [0, 1, 0, 1, 1, 0, 0, 1];
const N = 7;
console.log(prisonAfterNDays(cells, N));#include <stdio.h>
#include <string.h>
int findCycle(int *cells) {
int seen[256][8], cycleLength = 0;
while (cycleLength < 256) {
for (int i = 1; i < 7; ++i) {
cells[i] = cells[i - 1] == cells[i + 1];
}
cells[0] = cells[7] = 0;
int found = 0;
for (int i = 0; i < cycleLength; ++i) {
if (memcmp(seen[i], cells, 8 * sizeof(int)) == 0) found = 1;
}
if (found) break;
memcpy(seen[cycleLength++], cells, 8 * sizeof(int));
}
return cycleLength;
}
void prisonAfterNDays(int *cells, int n) {
int cycle = findCycle(cells);
n = n % cycle == 0 ? cycle : n % cycle;
for (int i = 0; i < n; ++i) {
int newCells[8];
for (int j = 1; j < 7; ++j) {
newCells[j] = cells[j - 1] == cells[j + 1];
}
newCells[0] = newCells[7] = 0;
memcpy(cells, newCells, 8 * sizeof(int));
}
}
int main() {
int cells[8] = {0, 1, 0, 1, 1, 0, 0, 1};
int n = 7;
prisonAfterNDays(cells, n);
for(int i = 0; i < 8; i++) {
printf("%d ", cells[i]);
}
return 0;
}using System;
using System.Collections.Generic;
public class PrisonCells {
public static string CellsToString(int[] cells) {
return string.Join("", cells);
}
public static int[] PrisonAfterNDays(int[] cells, int N) {
var seen = new Dictionary<string, int>();
int cycle = 0;
while (N > 0) {
string cellState = CellsToString(cells);
if (seen.ContainsKey(cellState)) {
N %= cycle - seen[cellState];
}
seen[cellState] = cycle;
if (N > 0) {
N--;
int[] next = new int[8];
for (int i = 1; i < 7; ++i) {
next[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
}
Array.Copy(next, cells, 8);
cycle++;
}
}
return cells;
}
public static void Main(string[] args) {
int[] cells = new int[] {0, 1, 0, 1, 1, 0, 0, 1};
int N = 7;
int[] result = PrisonAfterNDays(cells, N);
Console.WriteLine(string.Join(", ", result));
}
}In Python, this approach uses dictionaries to remember sequences of day states and the corresponding day of occurrence. The pyplot library helps determine repetitive sequences and adjust further computations when 'N' exceeds a full cycle.
Time complexity is O(128), characterized by all unique states exploration.
Space complexity: O(128) for storing state strings up to 128 in length.
Complexity comparison
| Approach | Complexity |
|---|---|
| Simulate Each Day | Time complexity: O(1). Limited to cycle evaluation. |
| Identify Cycle in States | Time complexity is O(128), characterized by all unique states exploration. |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Each Day | O(N) | O(1) | Small N where direct simulation is sufficient and implementation simplicity matters |
| Identify Cycle in States | O(min(N, cycle)) ≈ O(1) | O(64) | Large N (up to 1e9). Detect repeating states with hashing and skip cycles |
Frequently asked questions
Is Prison Cells After N Days easy or hard?
The problem is rated Medium because the rules are simple but recognizing the repeating cycle is the main challenge. A brute-force simulation is straightforward, but the optimized cycle detection solution demonstrates stronger algorithmic insight.
Prison Cells After N Days Python/Java solution
Python and Java implementations usually simulate the next state using a loop from index 1 to 6 and check whether neighbors are equal. The optimized version stores each state in a hash map or set to detect cycles and uses modulo arithmetic to skip repeated days.
How to solve Prison Cells After N Days in O(1)?
Store each daily configuration in a hash map or set and stop when a state repeats. Because only 6 cells change, the number of possible states is limited. After detecting the cycle length, reduce N with modulo arithmetic (N % cycle_length) and simulate the remaining days. This keeps the runtime independent of large N values.
What is the best approach for Prison Cells After N Days?
The most efficient approach detects cycles in the cell states using a hash table. Since the first and last cells always become 0, only the 6 middle cells vary, giving at most 64 unique states. Once a repeating configuration appears, compute N % cycle_length and simulate only the remaining steps. This reduces the effective complexity to constant time.
Is Prison Cells After N Days asked at Google/Amazon/Meta?
Cycle detection and state simulation problems similar to this appear in interviews at companies like Amazon and Google. The problem tests array simulation, hashing, and recognizing repeating patterns in constrained state spaces.
What data structure is used in Prison Cells After N Days?
The solution primarily uses an array to represent the 8 prison cells and a hash table or hash set to store previously seen states. Some optimized implementations encode the array as a bitmask integer using bit manipulation for faster comparisons.
What is the time complexity of Prison Cells After N Days?
A naive simulation runs in O(N) time because you compute the next state for each day. The optimized solution uses cycle detection and runs in O(min(N, cycle_length)), where the cycle is at most 64 states. In practice this behaves like O(1) time with O(64) space.