Leetcode discuss: 957. Prison Cells After N Days

 Here is the link. 

C# | Quick learner in 30 minutes | TLE concern in algorithm design | using HashSet

May 10, 2022
Introduction
To be a quick learner, I always like to read at least three solutions, and also write C# solutions based on Leetcode discuss posts shared by others.

Analysis | Intuition | votrubac
Based on the following constraints given in problem statement, we can easily to discuss the scope of problem based on n in range of 2^9, cells.Length = 8.

Constraints:

cells.length == 8
cells[i] is either 0 or 1.
1 <= n <= 10^9

If cells's length is 8, in other words, there are 8 cells, since each cell is either 0 or 1, so the number of all the possible state combinations is 2^8 = 256. This means when N > 256, cells will have the same state as its orignal 256 states. So we expedite the search, avoid time out, reduce calculatuion of next state from n to [loop size] + n % [loop size]. It is challenge task to determine how to take minimum calculation approach in design stage.

For example, given n = 1,000,000, cells is an integer array with size 8, so the total steps to calculate is reduced from n to 256 + n %256, which is at most 512. Reduction from 1,000,000 to 512 is big success to solve this problem without TLE problem.

Using 2^8 vs HashSet | Random state
Since integer array cells's length - denoted as L determines at most 2^L states, it is random process to determine next state, so we can not determine how many states to end the cycle, therefore, we need to store all possible states and use HashSet to determine if it is seen in previous steps.

Of course, it is a good practice to write a solution using bit manipulation. I will try it as well.

Complexity Analysis
Runtime: O(2 ^ n), where n is the number of cells (not days). For 8 cells, we can have 64 different states.

Memory: O(n). We need to remember a single state of all cells for the loop detection. For 8 cells, the complexity is O(1).

I just warmup the algorithm using less than 30 minutes.

The following C# code passes online judge.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _957_prison_cells_after_N_days
{
    class Program
    {
        static void Main(string[] args)
        {
            //Input: cells = [0,1,0,1,1,0,0,1], n = 7
            //Output: [0,0,1,1,0,0,0,0]
            var test = new Program();
            var result = test.PrisonAfterNDays(new int[] { 0, 1, 0, 1, 1, 0, 0, 1 }, 7);
            Debug.Assert(String.Join(",", result).CompareTo("0,0,1,1,0,0,0,0") == 0);
        }

        /// <summary>
        /// study code
        /// https://leetcode.com/problems/prison-cells-after-n-days/discuss/634109/C-solution
        /// </summary>
        /// <param name="cells"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public int[] PrisonAfterNDays(int[] cells, int n)
        {
            if (cells == null || cells.Length == 0 || n <= 0)
            {
                return new int[0];
            }

            // store all the seen/visited states 
            var seen = new HashSet<string>();
            var count = 0;

            var length = cells.Length;
            var nextState = new int[length];
            while (n > 0)
            {
                nextState = getNextState(cells);
                var state = string.Join("", nextState);

                if (seen.Contains(state))
                {
                    break;
                }

                seen.Add(state);

                // only update cells when its state was not seen before
                // the state will be the starting state for the remaining n%k days
                Array.Copy(nextState, cells, length);

                // count the actaul no. of days that have no duplicated states
                count++;
                n--;
            }

            // update the state for the remaining n%k days
            n %= count;
            while (n > 0)
            {
                cells = getNextState(cells);
                n--;
            }

            return cells;
        }

        /// <summary>
        /// If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
        /// Otherwise, it becomes vacant.
        /// </summary>
        /// <param name="cells"></param>
        /// <returns></returns>
        private int[] getNextState(int[] cells)
        {
            var length = cells.Length;
            // default is zero - vacant 
            var nextDayCells = new int[length]; 

            for (int i = 1; i < length - 1; i++)
            {
                if (cells[i - 1] == cells[i + 1])
                {
                    nextDayCells[i] = 1;
                }
            }

            return nextDayCells;
        }
    }
}