Prison cells after n days

Array Hash Table Math Bit Manipulation

39.1% acceptance

Feb 25, 2026

1559

1779

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).

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn prison_after_n_days(cells: Vec<i32>, n: i32) -> Vec<i32> {
    let mut cells = cells;
    let mut seen = std::collections::HashMap::new();
    let mut n = n;
    while n > 0 {
      let key = cells.clone();
      if let Some(&prev_n) = seen.get(&key) {
        let cycle = prev_n - n;
        n %= cycle;
        if n == 0 { break; }
      }
      seen.insert(key, n);
      let mut next = vec![0; 8];
      for i in 1..7 { next[i] = if cells[i-1] == cells[i+1] { 1 } else { 0 }; }
      cells = next;
      n -= 1;
    }
    cells
  }
}