LeetCode 2237 - Count Positions on Street With Required Brightness

The problem describes a street represented by positions from 0 to n - 1. There are multiple street lamps, each defined by its position and range. A lamp at position p with range r illuminates all positions from max(0, p - r) to min(n - 1, p + r), inclusive.

leetcodemediumarrayprefix-sum

LeetCode Problem 2237

Difficulty: 🟡 Medium
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem describes a street represented by positions from 0 to n - 1. There are multiple street lamps, each defined by its position and range. A lamp at position p with range r illuminates all positions from max(0, p - r) to min(n - 1, p + r), inclusive. The brightness of a position is the number of lamps covering that position.

We are also given an array requirement where requirement[i] represents the minimum brightness required at position i. Our goal is to count how many positions meet or exceed their brightness requirement.

The input constraints tell us that n and the number of lamps can be as large as 10^5. A naive solution iterating over all positions for every lamp could be O(n * m), which is too slow. The problem guarantees that positions and ranges are valid, and the requirement array matches the street length.

Edge cases include a street with only one position, lamps with zero range, positions that are not covered by any lamp, and positions where the requirement is zero.

Approaches

The brute-force approach would iterate over each lamp and increment the brightness of every position it covers. Then, for each position, check if the brightness meets the requirement. While this is correct, it is inefficient because each lamp could affect up to O(n) positions, leading to a time complexity of O(n * m) for m lamps, which is unacceptable for large inputs.

The optimal approach uses a prefix sum technique, also called the difference array method. Instead of incrementing every position individually for each lamp, we increment the start of the range and decrement the position just after the end of the range. After processing all lamps, a single pass computes the cumulative sum, giving the brightness at each position efficiently. This reduces the time complexity to O(n + m), which is suitable for the input limits.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(n) Increment brightness for every position for each lamp
Optimal O(n + m) O(n) Use prefix sum / difference array to efficiently compute brightness

Algorithm Walkthrough

  1. Initialize an array brightness of size n + 1 with all zeros. We use n + 1 to simplify range decrement operations.
  2. Iterate through each lamp [position, range]:
  • Compute the start of the coverage as max(0, position - range).
  • Compute the end of the coverage as min(n - 1, position + range).
  • Increment brightness[start] by 1.
  • Decrement brightness[end + 1] by 1, if end + 1 < n.
  1. Convert the brightness difference array into actual brightness values by iterating from left to right and maintaining a running sum.
  2. Count positions where brightness[i] >= requirement[i].
  3. Return the count.

Why it works: Using a difference array ensures that we only perform two updates per lamp instead of updating each covered position. The running sum translates the difference array into actual brightness, giving the correct number of lamps covering each position.

Python Solution

from typing import List

class Solution:
    def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:
        brightness = [0] * (n + 1)
        
        for position, r in lights:
            start = max(0, position - r)
            end = min(n - 1, position + r)
            brightness[start] += 1
            if end + 1 < n:
                brightness[end + 1] -= 1
        
        # Compute prefix sum to get actual brightness
        for i in range(1, n):
            brightness[i] += brightness[i - 1]
        
        count = 0
        for i in range(n):
            if brightness[i] >= requirement[i]:
                count += 1
        
        return count

The implementation first builds the difference array and then computes the prefix sum to get actual brightness at each position. The final loop counts the positions satisfying the requirement.

Go Solution

func meetRequirement(n int, lights [][]int, requirement []int) int {
    brightness := make([]int, n+1)

    for _, light := range lights {
        pos, r := light[0], light[1]
        start := pos - r
        if start < 0 {
            start = 0
        }
        end := pos + r
        if end >= n {
            end = n - 1
        }
        brightness[start] += 1
        if end+1 < n {
            brightness[end+1] -= 1
        }
    }

    // Prefix sum to compute actual brightness
    for i := 1; i < n; i++ {
        brightness[i] += brightness[i-1]
    }

    count := 0
    for i := 0; i < n; i++ {
        if brightness[i] >= requirement[i] {
            count++
        }
    }

    return count
}

In Go, we use a slice of size n + 1 to handle the difference array. Edge cases like end + 1 beyond the array are handled carefully, similar to Python.

Worked Examples

Example 1:

n = 5, lights = [[0,1],[2,1],[3,2]], requirement = [0,2,1,4,1]

Step by step:

  1. Initialize brightness = [0,0,0,0,0,0].
  2. Process lamp [0,1] → start=0, end=1 → brightness = [1,0,-1,0,0,0].
  3. Process lamp [2,1] → start=1, end=3 → brightness = [1,1,-1,-1,-0,0].
  4. Process lamp [3,2] → start=1, end=4 → brightness = [1,2,-1,-1,-1,0].
  5. Prefix sum → brightness = [1,3,2,1,0].
  6. Compare to requirement → positions 0,1,2,4 meet requirement → result 4.

Example 2:

n = 1, lights = [[0,1]], requirement = [2]

  1. Initialize brightness = [0,0].
  2. Lamp [0,1] → start=0, end=0 → brightness = [1,0].
  3. Prefix sum → brightness = [1].
  4. Compare to requirement → 1 < 2 → result 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) One pass to build difference array (O(m)), one pass for prefix sum (O(n)), one pass to count positions (O(n))
Space O(n) Difference array of size n+1

The algorithm is efficient even for the largest constraints (n, m <= 10^5), as it uses linear time and space.

Test Cases

# Provided examples
assert Solution().meetRequirement(5, [[0,1],[2,1],[3,2]], [0,2,1,4,1]) == 4
assert Solution().meetRequirement(1, [[0,1]], [2]) == 0

# Edge cases
assert Solution().meetRequirement(1, [[0,0]], [0]) == 1  # Single lamp, single position, requirement zero
assert Solution().meetRequirement(1, [[0,0]], [1]) == 1  # Single lamp, range 0, requirement met
assert Solution().meetRequirement(5, [[1,0],[3,0]], [0,1,0,1,0]) == 2  # Lamps with zero range
assert Solution().meetRequirement(5, [[0,10]], [0,0,0,0,0]) == 5  # Lamp covers all positions
Test Why
Example 1 Validates multiple lamps overlapping and requirement comparison
Example 2 Single position, requirement higher than brightness
Single lamp, zero range, requirement 0 Edge case where requirement is trivially met
Single lamp, zero range, requirement 1 Edge case where single lamp covers requirement
Multiple zero-range lamps Lamps affect only one position each
Lamp covers entire street Ensures prefix sum works for large ranges

Edge Cases

  1. Single position street: The street has only one position. This is tricky because the algorithm must handle arrays of size 1 correctly. Both Python and Go implementations handle this naturally, including the difference array edge.
  2. Lamp with zero range: Lamps may illuminate only their own position. This tests whether the algorithm correctly calculates start = end = position and updates the difference array correctly.
  3. Position with requirement 0: Positions where the requirement is zero should always count, regardless of the number of lamps. The implementation handles this because we directly compare brightness[i] >= requirement[i].

These edge cases validate that the