# Street Play in HackerLand

March 10, 2023

## Problem

The Film and Theater Society of HackerLand is preparing for a street play next month, which will take place on a stage that is *n* meters long and has *m* lights positioned above it. Each light can emit one of three colors: red, blue, or green. When a range of the stage is illuminated by all three colors, it appears white. Each light illuminates a specific range on the stage, which is defined by three attributes: color, left, and right. Color is represented by the integers 1, 2, or 3 to denote red, blue, and green, respectively, while left and right indicate the range of the stage that the light illuminates.

Your task is to determine the total number of integer positions on the stage that are illuminated with white light.
**Example**

The stage is *n = 5* meters long and has *m = 3* lights above it.

`lights = [[1, 1, 5], [2, 2, 5], [3, 3, 5]]`

shown as *[color, left, right]*

- Light
`1`

is red and covers a range from 1 to 5. - Light
`2`

is blue and covers a range from 2 to 5. - Light
`3`

is green and covers a range from 3 to 5.

The range [3, 5], locations 3, 4, and 5 receive white light. Return 3.

**Function Description**

Complete the function *getWhiteLightLength* .

*getWhiteLightLength* has the following parameter(s):

*int* *n:* the length of the stage

*int* *m:* the number of lights

*int* *lights[m][3]:* each row is [color, left, right]

**Returns**

*int:* the number of integer locations illuminated by white light

**Constraints**

- $1 ≤ n ≤ 10^5$
- $1 ≤ m ≤ 10^5$
- $1 ≤ lights[i][0] ≤ 3$
- $1 ≤ lights[i][1] ≤ lights[i][2] ≤ n$

Input Format for Custom Testing

- The first line contains an integer
*n*, the length of the stage. - The second line contains an integer
*m*, the number of lights. - The third line contains an integer,
*m,*the number of rows of the*lights*array. - The fourth line contains
*3,*the number of columns of the*lights*array.

Each of the next `m`

lines contains three integers `lights[i][0]`

, `lights[i][1]`

and `lights[i][2]`

.

## Case 0

### Sample Case 0

**Sample Input 0**

STDIN FUNCTION----- --------5 → n = 53 → m = 33 → the rows of lights[] m = 33 → the columns of lights[] = 31 1 3 → lights = [[1, 1, 3], [2, 2, 4], [3, 3, 5]]2 2 43 3 5

**Sample Output 0**

1

**Explanation**

Only range `[3, 3]`

has all three colors so the answer is 1.

## Case 1

**Sample Input 1**

STDIN FUNCTION----- --------5 → n = 54 → m = 44 → the rows of lights[] m = 43 → the columns of lights[] = 31 1 5 → lights = [[1, 1, 5], [1, 2, 4], [2, 2, 4], [3, 2, 4]]1 2 42 2 43 2 4

**Sample Output 1**

3

**Explanation**

Only range `[2, 4]`

has all three colors.

## Solution

Before continue how to solve the problem step by step let's breakdown the important information using simple question:

### How to determind white light programmatically?

Since the light is constant array [1,2,3] we can apply similar logic to file permission using bitwise operation.

- White light is represent all 3 lights is up can be represent using binary
`111`

= decimal`7`

- light [1,2,3] will be reduced by 1 convert to binary, for example
`1 << (color-1)`

then result from [1,2,3] -> decimal`[1,2,4]`

or binary`[001, 010, 100]`

- Use bitwise operator
`OR`

to append values.`1|2|3`

is equal with 7

### Better way to lights up from left to right

For brute force solution I just use iteration from left to right to lights up positions, for the optimized solution we can use suffix sum approach similar with previous post Array Manipulation

### Let's Solve it

- Initialize a variable
`numWhite`

to count the number of positions where all three bits are set - Initialize an array
`counts`

to count the number of times each position is illuminated - Loop through the lights and increment the counts for each illuminated position
- Lights up from left to right with given color
- If after lights up if the index is show white light then increment
`numWhite`

package mainimport "testing"func getWhiteLightLength(n int, m int, lights [][]int) int { // Initialize a variable to count the number of positions where all three bits are set numWhite := 0 // Initialize an array to count the number of times each position is illuminated counts := make([]int, n+1) // Loop through the lights and increment the counts for each illuminated position for _, light := range lights { color, left, right := light[0], light[1], light[2] for i := left; i <= right; i++ { // Use a bitmask to set the corresponding bit for the color counts[i] |= 1 << uint(color-1) // Check if all three bits are set for the current position if counts[i] == 7 { numWhite++ } } } return numWhite}func TestLight(t *testing.T) { tests := []struct { m int n int lights [][]int want int }{ {m: 4, n: 5, lights: [][]int{{1, 1, 5}, {1, 2, 4}, {2, 2, 4}, {3, 2, 4}}, want: 3}, {m: 3, n: 5, lights: [][]int{{1, 1, 3}, {2, 2, 4}, {3, 3, 5}}, want: 1}, } for _, tt := range tests { if got := getWhiteLightLength(tt.n, tt.m, tt.lights); got != tt.want { t.Errorf("getWhiteLightLengthOptimized(%v, %v, %v) = %v, want %v", tt.n, tt.m, tt.lights, got, tt.want) } }}

Try it yourself https://go.dev/play/p/-QvLi_hFE1M (opens in a new tab)

The time complexity of this code is $O(nm)$, where n is the size of the array counts and m is the number of lights.

The reason is that the code loops through the lights and for each light, it loops through all the positions from left to right, which is at most n. For each position, it sets a bit in the counts array and checks if all three bits are set, which takes constant time.

Therefore, the time complexity of the code is proportional to the number of lights times the maximum number of positions illuminated by a single light, which is at most n.

### Optimized version using prefix sum

The key point of the optimization step is to eliminate inner loop from `left`

to `right`

. Here the step:

- Remove the looping and replace it with set color values in binary in left index and right index inclusive. The left index with
`OR`

operator and the right with minus.

color, left, right := light[0], light[1], light[2]counts[left-1] |= 1 << uint(color-1)if right < n { // make sure to prevent out of bound counts[right] -= 1 << uint(color-1)}

- The next step is iterate
`counts`

to get sum values

for i := range counts { sum |= counts[i] if sum >= 7 { numWhite++ }}

Here is the complete implementation with unit testing.

package mainimport ( "fmt" "testing")func getWhiteLightLength(n int, m int, lights [][]int) int { // Initialize a variable to count the number of positions where all three bits are set numWhite := 0 // Initialize an array to count the number of times each position is illuminated counts := make([]int, n+1) // Loop through the lights and increment the counts for each illuminated position for _, light := range lights { color, left, right := light[0], light[1], light[2] counts[left-1] |= 1 << uint(color-1) if right < n { counts[right] -= 1 << uint(color-1) } } sum := 0 fmt.Println(counts) for i := range counts { sum |= counts[i] fmt.Println(sum) if sum >= 7 { numWhite++ } } return numWhite}func TestLight(t *testing.T) { tests := []struct { m int n int lights [][]int want int }{ {m: 4, n: 5, lights: [][]int{{1, 1, 5}, {1, 2, 4}, {2, 2, 4}, {3, 2, 4}}, want: 3}, {m: 3, n: 5, lights: [][]int{{1, 1, 3}, {2, 2, 4}, {3, 3, 5}}, want: 1}, {m: 3, n: 5, lights: [][]int{{1, 1, 5}, {2, 2, 4}, {3, 2, 5}}, want: 3}, {m: 3, n: 5, lights: [][]int{{1, 1, 4}, {2, 1, 4}, {3, 1, 4}, {3, 1, 5}}, want: 4}, } for _, tt := range tests { if got := getWhiteLightLength(tt.n, tt.m, tt.lights); got != tt.want { t.Errorf("getWhiteLightLengthOptimized(%v, %v, %v) = %v, want %v", tt.n, tt.m, tt.lights, got, tt.want) } }}

As always you can try yourself at https://go.dev/play/p/esryseOR0Qp (opens in a new tab).

The time complexity of the optimized function is $O(n)$, where n is the length of the `counts`

array.

The function loops through the `lights`

array once and performs constant time operations for each light. The `counts`

array is initialized with a constant amount of memory, and its length is only increased by 1. Thus, the loop through the `counts`

array also takes constant time per iteration.

Therefore, the overall time complexity of the function is O(n), where n is the length of the `counts`

array.