MediumArrayPrefix SumUpdated Sep 2026

2237. Count Positions on Street With Required Brightness

Asked at Capital One

Difficulty

Medium

Time

O(n + lights.length)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given a street with n positions, numbered 0 to n - 1. You are also given a list of street lamps. Each lamp is a pair [position, range]. A lamp at position with range lights up every position from position - range to position + range, but only inside the street. So the lit area is [max(0, position - range), min(n - 1, position + range)], and both ends are included.

The brightness of a position is simply how many lamps light it. You are given an array requirement of length n, where requirement[i] is the minimum brightness position i needs.

Return the number of positions whose brightness is greater than or equal to their requirement. Positions that are too dark do not count.

Three lamps, five positions

positions0123401234The street has 5 positions, numbered 0 to 4.lamp [0,1] coverslitlit---01234Lamp at 0 with range 1 lights positions 0 and 1.lamp [2,1] covers-litlitlit-01234Lamp at 2 with range 1 lights positions 1, 2 and 3.lamp [3,2] covers-litlitlitlit01234Lamp at 3 with range 2 lights positions 1 through 4.
Each lamp lights a range of positions; a position's brightness is how many ranges cover it.

Constraints

  • ●1 <= n <= 10^5
  • ●1 <= lights.length <= 10^5
  • ●0 <= positioni < n
  • ●0 <= rangei <= 10^5
  • ●requirement.length == n
  • ●0 <= requirement[i] <= 10^5

Examples

Example 1
Inputn = 5, lights = [[0,1],[2,1],[3,2]], requirement = [0,2,1,4,1]
Output4
WhyThe lamps cover [0,1], [1,3] and [1,4]. Adding them up gives brightness [1,3,2,2,1]. Compare with the requirement [0,2,1,4,1]: positions 0, 1, 2 and 4 meet it, but position 3 has brightness 2 and needs 4. So 4 positions pass.
Example 2
Inputn = 1, lights = [[0,1]], requirement = [2]
Output0
WhyThe single lamp covers only position 0, so the brightness there is 1. The requirement is 2, which is higher, so no position passes.

Asked At

1 companies
CompanyDifficulty
Capital OneMediumView all Capital One questions →

How to Think About It

1

Adding 1 to every position a lamp covers is O(n) per lamp — O(n * lamps) total.

2

Key insight: a difference array records only where coverage starts and stops. For a lamp covering [lo, hi], do diff[lo] += 1 and diff[hi + 1] -= 1.

3

A running prefix sum over diff then gives the exact brightness at each position in one pass.

4

Clip ranges to the street: lo = max(0, p - r), hi = min(n - 1, p + r).

5

Walkthrough: n = 5, lamps [0,1], [2,1], [3,2] cover [0,1], [1,3], [1,4]. Brightness [1,3,2,2,1]; compare with requirement and count matches.

Optimal Approach

Step 1: diff = [0] * (n + 1).
Step 2: For each lamp (p, r): diff[max(0, p - r)] += 1, diff[min(n - 1, p + r) + 1] -= 1.
Step 3: Running sum cur; for each position i, cur += diff[i]; count positions where cur >= requirement[i].
Step 4: Return the count.

Time: O(n + lamps). Space: O(n).

Difference array + prefix sum

diff (start/stop marks)120-1-2-1012345Each lamp does +1 at its left end and -1 just afterits right end.brightness (running sum)1322101234Adding diff left to right gives brightness[1,3,2,2,1]; the green positions meet theirrequirement.diff[lo] += 1diff[hi + 1] -= 1cur += diff[i]count if cur >= requirement[i]
Mark where each lamp starts and stops, then a running sum turns those marks into the brightness of every position.
ComplexityTime O(n + lights.length)Space O(n)Each lamp writes two entries in the difference array, and one prefix-sum pass over n positions gives every brightness.

What Trips People Up in Real Interviews

1

Incrementing every covered position per lamp — quadratic in the worst case.

2

Forgetting to clip the range to [0, n - 1], which writes out of bounds.

3

Allocating diff with size n and then writing to index n for lamps reaching the end.

4

Counting positions with brightness exactly equal to the requirement instead of at least.

Solution Code

O(n + lights.length) time
def meetRequirement(n, lights, requirement):
    diff = [0] * (n + 1)
    for p, r in lights:
        diff[max(0, p - r)] += 1
        diff[min(n - 1, p + r) + 1] -= 1
    count = cur = 0
    for i in range(n):
        cur += diff[i]
        if cur >= requirement[i]:
            count += 1
    return count

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Count Positions on Street With Required Brightness problem?

Count Positions on Street With Required Brightness gives you a street of `n` positions and lamps that each light a range `[p - r, p + r]` (clipped to the street). Each position has a required brightness. How many positions are lit by at least the required number of lamps? It is a textbook difference-array problem.

How do you solve Count Positions on Street With Required Brightness?

The optimal approach runs in O(n + lights.length) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Count Positions on Street With Required Brightness?

Count Positions on Street With Required Brightness is asked at Capital One. It is a medium difficulty problem.

What are common mistakes on Count Positions on Street With Required Brightness?
  • Incrementing every covered position per lamp — quadratic in the worst case.
  • Forgetting to clip the range to `[0, n - 1]`, which writes out of bounds.
  • Allocating `diff` with size `n` and then writing to index `n` for lamps reaching the end.
  • Counting positions with brightness exactly equal to the requirement instead of at least.