- Published on

# Street Play in HackerLand

- Authors
- Name
- Moch Lutfi
- @kaptenupi

## 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**

_9STDIN FUNCTION_9----- --------_95 → n = 5_93 → m = 3_93 → the rows of lights[] m = 3_93 → the columns of lights[] = 3_91 1 3 → lights = [[1, 1, 3], [2, 2, 4], [3, 3, 5]]_92 2 4_93 3 5

**Sample Output 0**

_11

**Explanation**

Only range `[3, 3]`

has all three colors so the answer is 1.

## Case 1

**Sample Input 1**

_10STDIN FUNCTION_10----- --------_105 → n = 5_104 → m = 4_104 → the rows of lights[] m = 4_103 → the columns of lights[] = 3_101 1 5 → lights = [[1, 1, 5], [1, 2, 4], [2, 2, 4], [3, 2, 4]]_101 2 4_102 2 4_103 2 4

**Sample Output 1**

_13

**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`

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

Try it yourself https://go.dev/play/p/-QvLi_hFE1M

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.

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

- The next step is iterate
`counts`

to get sum values

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

Here is the complete implementation with unit testing.

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

As always you can try yourself at https://go.dev/play/p/esryseOR0Qp.

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.