Problem Description

You have a straight street represented as a number line from 0 to n - 1. There are street lamps placed at various positions along this street.

Each street lamp is described by two values:

• position_i: where the lamp is located on the street
• range_i: how far the lamp's light reaches in both directions

A lamp at position position_i with range range_i illuminates all positions from max(0, position_i - range_i) to min(n - 1, position_i + range_i) inclusive. This means the lamp lights up positions within its range but doesn't go beyond the street boundaries (0 and n-1).

The brightness of any position on the street equals the total number of lamps that illuminate that position. For example, if 3 different lamps illuminate position 5, then position 5 has a brightness of 3.

You're given an array requirement where requirement[i] specifies the minimum brightness needed at position i.

Your task is to count how many positions on the street meet or exceed their brightness requirement. In other words, count the positions where the actual brightness is greater than or equal to the required brightness.

Example: If a position needs brightness of 2 (requirement) and 3 lamps illuminate it (actual brightness = 3), this position meets the requirement and should be counted.

The function should return the total number of positions between 0 and n - 1 that satisfy their brightness requirements.

Intuition

The key insight is that we need to efficiently track how many lamps illuminate each position on the street. A naive approach would be to iterate through each lamp and mark every position it illuminates, but this could be inefficient when lamps have large ranges.

Instead, we can use a difference array technique. The idea is that when a lamp illuminates a continuous range of positions, rather than updating each position individually, we only mark the boundaries of the range.

Think of it like this: when a lamp starts illuminating at position i, we mark "+1 lamp starts here". When the lamp stops illuminating after position j, we mark "-1 lamp ends here".

For example, if a lamp illuminates positions [2, 5], we put:

• +1 at position 2 (a lamp starts illuminating here)
• -1 at position 6 (a lamp stops illuminating after position 5)

When we later compute the prefix sum of these markers, the running sum at any position tells us exactly how many lamps are illuminating that position. This works because:

• Each +1 we encounter means a new lamp range has started
• Each -1 we encounter means a lamp range has ended
• The cumulative sum gives us the total number of active lamp ranges at each position

This transforms our problem from "update many positions for each lamp" to "update only 2 positions for each lamp", followed by a single pass to compute prefix sums. Once we have the brightness at each position through the prefix sum, we simply compare it with the requirement array to count positions that meet their minimum brightness requirement.

Learn more about Prefix Sum patterns.

Solution Approach

We implement the solution using a difference array technique:

1. Initialize the difference array: Create an array d of size n + 1 (one extra position to handle the boundary). Initialize all values to 0.

2. Process each street lamp: For each lamp at position p with range r:

   • Calculate the left boundary of illumination: i = max(0, p - r) (ensuring we don't go below position 0)
   • Calculate the right boundary of illumination: j = min(n - 1, p + r) (ensuring we don't exceed position n-1)
   • Mark the start of illumination: d[i] += 1
   • Mark the end of illumination: d[j + 1] -= 1

3. Compute actual brightness using prefix sum: Apply the accumulate function to the difference array d. This gives us the actual brightness at each position. The prefix sum works because:

   • Starting from position 0, we accumulate the difference values
   • Each +1 increases the running count (a lamp range starts)
   • Each -1 decreases the running count (a lamp range ends)
   • The accumulated value at position i equals the number of lamps illuminating that position

4. Count positions meeting requirements: Compare the actual brightness (from the prefix sum) with the required brightness at each position. Use zip to pair up the accumulated brightness values with the requirements, and count how many positions have brightness >= requirement.

The final expression sum(s >= r for s, r in zip(accumulate(d), requirement)) elegantly combines steps 3 and 4:

• accumulate(d) generates the brightness values
• zip pairs each brightness with its corresponding requirement
• The generator expression checks if each position meets its requirement
• sum counts the total number of positions that satisfy the condition

This approach has a time complexity of O(m + n) where m is the number of lamps and n is the street length, which is much more efficient than the naive O(m * n) approach.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• Street length: n = 7 (positions 0 to 6)
• Street lamps: [[2, 2], [5, 1]]
  • Lamp 1: position 2, range 2 (illuminates positions 0-4)
  • Lamp 2: position 5, range 1 (illuminates positions 4-6)
• Requirements: [1, 0, 2, 0, 1, 1, 0]

Step 1: Initialize difference array Create array d of size 8 (n+1):

d = [0, 0, 0, 0, 0, 0, 0, 0]

Step 2: Process each lamp

Lamp 1 (position=2, range=2):

• Left boundary: max(0, 2-2) = 0
• Right boundary: min(6, 2+2) = 4
• Mark boundaries: d[0] += 1, d[5] -= 1

d = [1, 0, 0, 0, 0, -1, 0, 0]

Lamp 2 (position=5, range=1):

• Left boundary: max(0, 5-1) = 4
• Right boundary: min(6, 5+1) = 6
• Mark boundaries: d[4] += 1, d[7] -= 1

d = [1, 0, 0, 0, 1, -1, 0, -1]

Step 3: Compute brightness using prefix sum Apply accumulate to get actual brightness at each position:

Position:    0  1  2  3  4  5  6
d values:    1  0  0  0  1  -1 0
Brightness:  1  1  1  1  2  1  1

The prefix sum works as:

• Position 0: 1 (one lamp range starts)
• Position 1: 1 (no change, still in same lamp range)
• Position 2-3: 1 (continuing same lamp range)
• Position 4: 2 (second lamp range starts, now two lamps overlap)
• Position 5: 1 (first lamp range ends, only second lamp remains)
• Position 6: 1 (second lamp continues)

Step 4: Count positions meeting requirements Compare brightness with requirements:

Position:     0  1  2  3  4  5  6
Brightness:   1  1  1  1  2  1  1
Requirement:  1  0  2  0  1  1  0
Meets req?:   ✓  ✓  ✗  ✓  ✓  ✓  ✓

• Position 0: 1 >= 1 ✓
• Position 1: 1 >= 0 ✓
• Position 2: 1 < 2 ✗
• Position 3: 1 >= 0 ✓
• Position 4: 2 >= 1 ✓
• Position 5: 1 >= 1 ✓
• Position 6: 1 >= 0 ✓

Result: 6 positions meet their brightness requirements.

Solution Implementation

Time and Space Complexity

The time complexity is O(m + n), where m is the number of lights and n is the number of positions. The algorithm iterates through all m lights to build the difference array (taking O(m) time), then uses accumulate to compute prefix sums over n positions and compares them with requirements (taking O(n) time). Since the reference answer simplifies this to O(n), it likely assumes m ≤ n in the worst case, making the overall complexity O(n).

The space complexity is O(n). The algorithm creates a difference array d of size n + 1 to track the changes in light coverage. The accumulate function generates values on-the-fly during iteration, and the final sum operation doesn't require additional space proportional to n. Therefore, the dominant space usage comes from the difference array, resulting in O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Range Boundaries

The Pitfall: A common mistake is incorrectly handling the range boundaries when marking the difference array. Developers might write:

# INCORRECT - marks wrong end boundary
diff_array[right_bound] -= 1  # Wrong!

Why it happens: The difference array technique requires marking the position after the range ends. Since a lamp illuminates positions from left_bound to right_bound inclusive, we need to decrement at right_bound + 1 to indicate the light stops affecting positions beyond right_bound.

Solution: Always mark the decrement at right_bound + 1:

# CORRECT
diff_array[right_bound + 1] -= 1

2. Insufficient Array Size

The Pitfall: Creating a difference array of size n instead of n + 1:

# INCORRECT - array too small
diff_array = [0] * n  # IndexError when right_bound = n-1

Why it happens: When right_bound = n - 1, we need to access diff_array[n] to mark the range end. Without the extra element, this causes an IndexError.

Solution: Always allocate n + 1 elements:

# CORRECT
diff_array = [0] * (n + 1)

3. Misunderstanding Accumulate Output Length

The Pitfall: Assuming accumulate(diff_array) returns exactly n elements when the input has n + 1 elements.

Why it happens: accumulate returns an iterator with the same number of elements as the input. Since diff_array has n + 1 elements, accumulate(diff_array) also yields n + 1 values, but we only need the first n for comparison with requirement.

Solution: The zip function naturally handles this by stopping at the shorter sequence (requirement has n elements), so the code works correctly. However, for clarity, you could explicitly slice:

# More explicit version
brightness_values = list(accumulate(diff_array))[:n]
positions_meeting_requirement = sum(
    brightness >= required 
    for brightness, required in zip(brightness_values, requirement)
)

4. Integer Overflow in Other Languages

The Pitfall: While not an issue in Python, implementing this in languages like C++ or Java requires careful consideration of integer overflow when many lamps overlap at the same position.

Solution: In Python, integers have arbitrary precision, so this isn't a concern. In other languages, use appropriate data types (e.g., long in Java, long long in C++) if the number of overlapping lamps could be large.