We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Positions on Street With Required Brightness

Number: 2385

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a street represented by positions 0 to n - 1, you have a list of street lamps where each lamp at position pos with range rng lights up the interval [max(0, pos - rng), min(n - 1, pos + rng)]. The brightness of a position is the number of lamps that light it up. Each position i has a required minimum brightness given by requirement[i]. The task is to count how many positions have a brightness that is at least as high as the required brightness.

Key Insights

  • Use a difference array to efficiently apply range updates derived from each lamp's coverage.
  • For each lamp, add 1 at the starting index of its coverage and subtract 1 after its ending index.
  • Leverage prefix sum on the difference array to obtain the brightness at each position.
  • Compare the computed brightness at each position with the given requirement.

Space and Time Complexity

Time Complexity: O(n + m), where m is the number of lights. Space Complexity: O(n)

Solution

We approach the problem using a difference array to handle the multiple range updates efficiently. For every street lamp, determine the start of its effect as max(0, pos - rng) and the end as min(n - 1, pos + rng). Increment the difference array at the start index, and decrement the position immediately after the end (if within bounds). After processing all lamps, a prefix sum on the difference array gives the overall brightness at every street position. Finally, we traverse the brightness array to count the positions where the brightness is at least the required level.

Code Solutions

# Python solution using a difference array and prefix sum.

def countPositions(n, lights, requirement):
    # Create a difference array with one extra element to handle boundary updates
    diff = [0] * (n + 1)
    
    # Apply range updates for each light
    for pos, rng in lights:
        start = max(0, pos - rng)  # Ensure we don't go below 0
        end = min(n - 1, pos + rng)  # Ensure we don't go above n - 1
        diff[start] += 1         # Increase brightness starting from 'start'
        if end + 1 < n:
            diff[end + 1] -= 1   # Decrease brightness after the 'end'
    
    # Compute the brightness by taking a prefix sum of the difference array
    brightness = [0] * n
    brightness[0] = diff[0]
    for i in range(1, n):
        brightness[i] = brightness[i - 1] + diff[i]
    
    # Count positions where brightness meets or exceeds requirement
    count = 0
    for i in range(n):
        if brightness[i] >= requirement[i]:
            count += 1
            
    return count

# Example usage:
n = 5
lights = [[0, 1], [2, 1], [3, 2]]
requirement = [0, 2, 1, 4, 1]
print(countPositions(n, lights, requirement))  # Expected output: 4
← Back to All Questions