Street Play in HackerLand

March 10, 2023

Name: Moch Lutfi
Twitter: @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

STDIN     FUNCTION
-----       --------
     →    n = 5
     →    m = 3
     →    the rows of lights[] m = 3
     →    the columns of lights[] = 3
1 3   →    lights = [[1, 1, 3], [2, 2, 4], [3, 3, 5]]
2 4
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
-----      --------
     →    n = 5
     →    m = 4
     →    the rows of lights[] m = 4
     →    the columns of lights[] = 3
1 5   →    lights = [[1, 1, 5], [1, 2, 4], [2, 2, 4], [3, 2, 4]]
2 4
2 4
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 main
import "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 main
import (
	"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.

System design interview Vowel Substring