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]: 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] ≤ 3$
• $1 ≤ lights[i] ≤ lights[i] ≤ 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], lights[i] and lights[i].

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

1. Initialize a variable numWhite to count the number of positions where all three bits are set
2. Initialize an array counts to count the number of times each position is illuminated
3. 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, light, light_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, light, light_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, light, light_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.