Taro Logo

Count Positions on Street With Required Brightness

Medium
Asked by:
Profile picture
79 views
Topics:
Arrays

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 <= 105
  • 1 <= lights.length <= 105
  • lights[i].length == 2
  • 0 <= positioni < n
  • 0 <= rangei < n
  • required.length == n
  • 0 <= required[i] <= 105

Solution


Clarifying Questions

When 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:

  1. What are the possible ranges for values in the `lights` array and the `brightness` array? Can they be negative, zero, or very large?
  2. What is the size limit for the input arrays `lights` and `brightness`? I want to understand the scale for performance considerations.
  3. If a position's actual brightness is less than the required brightness, should I still count that position? Or do I only count positions *meeting* the required brightness?
  4. What should I return if all positions on the street meet the required brightness?
  5. Are the `lights` and `brightness` arrays guaranteed to have the same length, and can they be empty?

Brute Force Solution

Approach

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:

  1. Start at the first position on the street.
  2. For that position, look at every light that's shining on it.
  3. Add up the brightness from all those lights to get the total brightness for that position.
  4. See if that total brightness is at least as bright as what's required.
  5. If it is, then count that position as being bright enough.
  6. Now, move to the next position on the street.
  7. Repeat steps 2 through 5 for this new position.
  8. Keep doing this until you've checked every single position on the street.
  9. In the end, the number of positions you counted as bright enough is your answer.

Code Implementation

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_count

Big(O) Analysis

Time Complexity
O(n*m) – The algorithm iterates through each position on the street (n positions). For each position, it iterates through all the lights (m lights) to calculate the total brightness at that position. Therefore, the total number of operations is proportional to the product of the number of positions and the number of lights. This gives us a time complexity of O(n*m), where n is the number of positions on the street and m is the number of lights. If we assume the number of lights 'm' can be proportional to the number of positions 'n', this would then become O(n²).
Space Complexity
O(1) – The brute force approach calculates the brightness for each position on the street independently. It doesn't require any extra data structures to store intermediate brightness values or track visited positions. Only a few constant space variables are used to iterate through the street positions and lights. Therefore, the space complexity is constant regardless of the number of street positions or lights.

Optimal Solution

Approach

The 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:

  1. Imagine each lamp adds brightness not just at its position, but also at all positions within its range.
  2. Instead of directly calculating brightness at each position, record where the brightness starts and where it ends for each lamp.
  3. When a lamp's influence starts at a position, increase the brightness value at that position. When its influence ends, decrease the brightness at that position.
  4. Go through each position on the street. Keep a running total of the brightness changes. This running total represents the actual brightness at each position.
  5. Compare the brightness at each position with the required brightness. If it meets or exceeds the requirement, count that position.
  6. After checking all positions, return the total count of positions that meet the required brightness.

Code Implementation

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

Big(O) Analysis

Time Complexity
O(n + lamps) – The algorithm iterates through the 'lamps' array to record the start and end positions of each lamp's influence which takes O(lamps) time where 'lamps' is the number of lamps. Then, the algorithm iterates through the street positions (n) to calculate the running sum of brightness and compare it to the required brightness. This step takes O(n) time. Therefore, the overall time complexity is O(n + lamps).
Space Complexity
O(N) – The algorithm uses an auxiliary data structure, specifically an array (or list), to store the brightness changes at each position on the street. The size of this array is directly proportional to the number of positions on the street, which we can denote as N. Therefore, the extra space required to track these brightness changes scales linearly with N, resulting in a space complexity of O(N).

Edge Cases

Null or empty street array
How to Handle:
Return 0, indicating no positions meet the criteria.
Empty lights array
How to Handle:
Treat all positions as having 0 additional brightness, so only inherent brightness matters.
Street array with a single position
How to Handle:
Check if that single position meets the required brightness, accounting for lights contributions.
Lights array with a single element spanning the entire street
How to Handle:
Add the full light contribution to each position on the street.
Large street and lights arrays potentially causing integer overflow when summing brightness
How to Handle:
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
How to Handle:
Ensure that we are not accessing the street array out of bounds when applying light contributions.
Negative brightness values in the street array
How to Handle:
Handle negative values as a valid starting brightness and correctly accumulate light contributions.
Positions with extremely high initial brightness values.
How to Handle:
Ensure cumulative brightness does not overflow, potentially using long and checking for overflows during the sum.