You are given an integer n representing the number of positions on a street. You are also given a 2D integer array lights where lights[i] = [positioni, rangei] indicates that the ith light is centered at positioni and has a range of rangei.
A position pos on the street has a brightness of b if there is at least one light such that |pos - positioni| <= rangei. You are given another integer array required of length n such that required[pos] is the minimum brightness of the position pos. The position is represented by its index.
Return the number of positions on the street that have a brightness of at least required[pos].
Example 1:
Input: n = 5, lights = [[1,3],[5,0],[2,2]], required = [0,2,1,4,0] Output: 2 Explanation: - The position 0 has a brightness of 1 because the light at position 1 covers it. - The position 1 has a brightness of 4 because the lights at positions 1 and 2 cover it. - The position 2 has a brightness of 3 because the lights at positions 1 and 2 cover it. - The position 3 has a brightness of 1 because the light at position 1 covers it. - The position 4 has a brightness of 0 because no light covers it. Only positions 1 and 2 have a brightness of at least the required brightness, required[1] = 2 and required[2] = 1.
Example 2:
Input: n = 1, lights = [[0,1]], required = [2] Output: 0 Explanation: The position 0 has a brightness of 1 because the light at position 0 covers it. Only positions 0 has a brightness of at least the required brightness, required[0] = 2.
Constraints:
1 <= n <= 1051 <= lights.length <= 105lights[i].length == 20 <= positioni < n0 <= rangei < nrequired.length == n0 <= required[i] <= 105When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force way to solve this problem is very straightforward. We will go through each position on the street and calculate its total brightness based on the given lights. Then, we'll check if that brightness meets the required amount.
Here's how the algorithm would work step-by-step:
def count_positions_brute_force(
street_length, lights, required_brightness
):
bright_positions_count = 0
for position in range(street_length):
total_brightness = 0
# Iterate through each light source to calculate brightness at the current position
for light_position, light_range, light_brightness in lights:
if (
position >= light_position - light_range
and position <= light_position + light_range
):
# Add brightness only if light covers the current position
total_brightness += light_brightness
# Check if the total brightness meets the requirement
if total_brightness >= required_brightness:
bright_positions_count += 1
return bright_positions_countThe key is to efficiently track the cumulative brightness effect of each lamp at each position without recomputing it repeatedly. We'll use a clever technique to keep track of the changes in brightness rather than the absolute brightness at each point. By using a running sum approach, we can find the final brightness with minimal work.
Here's how the algorithm would work step-by-step:
def count_positions_with_required_brightness(street_length, lamps, required_brightness):
brightness_changes = [0] * street_length
for position, lamp_range, lamp_power in lamps:
start_position = max(0, position - lamp_range)
end_position = min(street_length, position + lamp_range + 1)
# Increment brightness at the start position
brightness_changes[start_position] += lamp_power
# Decrement brightness at the end position to counter the addition.
if end_position < street_length:
brightness_changes[end_position] -= lamp_power
current_brightness = 0
bright_position_count = 0
for i in range(street_length):
# Accumulate brightness changes to get actual brightness.
current_brightness += brightness_changes[i]
# Count positions that meet the required brightness
if current_brightness >= required_brightness:
bright_position_count += 1
return bright_position_count| Case | How to Handle |
|---|---|
| Null or empty street array | Return 0, indicating no positions meet the criteria. |
| Empty lights array | Treat all positions as having 0 additional brightness, so only inherent brightness matters. |
| Street array with a single position | Check if that single position meets the required brightness, accounting for lights contributions. |
| Lights array with a single element spanning the entire street | Add the full light contribution to each position on the street. |
| Large street and lights arrays potentially causing integer overflow when summing brightness | Use a data type with a larger range, such as long, to store the cumulative brightness. |
| Lights with a large range value compared to the street size | Ensure that we are not accessing the street array out of bounds when applying light contributions. |
| Negative brightness values in the street array | Handle negative values as a valid starting brightness and correctly accumulate light contributions. |
| Positions with extremely high initial brightness values. | Ensure cumulative brightness does not overflow, potentially using long and checking for overflows during the sum. |