Leetcode discuss: 1375. Bulb Switcher III

Jan. 21, 2021

Here is the link. 

First practice - C# - O(1) to check all lights are blue - 30+ minutes

Jan. 21, 2021
Introduction
It is very good practice although I made it work in less than 48 minutes in mock onsite interview - Microsoft. I spent over 15 minutes to think about how to find any light should be set to blue using O(1) time, just check it's left neighbor.

Design issue
It took me at least 10 minutes to figure out how to use O(1) to check if the current light can set to blue or not.

The status array is declared to store all position light status, 0 - off, 1 - on, 2 - blue.

Any light can be changed from 'on'(1) to 'blue'(2) only once. It is easy to argue and prove it. When a light is set to blue, the right neighbor should be checked one by one if needed to change from on to blue.

For example, [2, 1, 3, 5, 4]
First light is at position of index = 1, second light is at position of index = 0 which should be blue (no left neighbor). Next to check it's right, index = 1, status[1] = 1, change it to 2.

Performance
It took me over 20 minutes to fix bugs. I mixed variable current with i inside for loop. It is better for me to name current variable with meaningful name to avoid mixing with i.

The current variable should be better named as placeHolder, left neighbor is placeHolder - 1, right neighbor is placeHolder + 1. I will think more later for better naming.

Time complexity
O(N), N is the length of the array

Space complexity
O(N), N is the length of the array

The following code passes online jduge

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

namespace TurnOnLights
{
    class Program
    {
        static void Main(string[] args)
        {
            var light = new int[] { 1, 6, 3, 4, 5, 7, 2, 8, 9, 10 };

            var result = NumTimesAllBlue(light); 
        }

        public static int NumTimesAllBlue(int[] light)
        {
            if (light == null || light.Length == 0)
            {
                return 0;
            }

            var length = light.Length;
            var status = new int[length]; // 0 - off, 1 - on, 2 - blue

            var count = 0;

            for (int i = 0; i < length; i++)
            {
                var current = light[i] - 1;

                status[current] = 1;
                if (current == 0 || (status[current - 1] == 2)) // mix i with current - take 10 minutes
                {
                    status[current] = 2;

                    //check right neighbors 
                    var index = current + 1; // mix i with current 
                    while (index < length && status[index] == 1)
                    {
                        status[index++] = 2;
                    }

                    if (index == (i + 1))
                    {
                        count++;
                    }
                }
            }

            return count; 
        }
    }
}