Count Positions on Street With Required Brightness
Asked at Capital One
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Capital One | Medium | View all Capital One questions → |
How to Think About It
Adding 1 to every position a lamp covers is O(n) per lamp — O(n * lamps) total.
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.
A running prefix sum over diff then gives the exact brightness at each position in one pass.
Clip ranges to the street: lo = max(0, p - r), hi = min(n - 1, p + r).
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).
What Trips People Up in Real Interviews
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.
Solution Code
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 countFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.