Count Street Positions Meeting Their Light Requirement
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
A street has integer positions from `0` through `n - 1`. A lamp `[position, range]` covers every position from `max(0, position - range)` through `min(n - 1, position + range)`, including both ends. The brightness at a position is the number of lamps covering it. Return how many positions have brightness at least their own minimum value in `requirement`.
```cpp
class Solution {
public:
int meetRequirement(int n, vector<vector<int>>& lights, vector<int>& requirement);
};
```
### Examples
**Example 1:**
```text
n = 4, lights = [[0,1],[3,1]], requirement = [1,2,0,1]
Output: 3
Explanation: Brightness is [1,1,1,1]; positions 0,2,3 qualify.
```
**Example 2:**
```text
n = 3, lights = [[1,0]], requirement = [0,1,1]
Output: 2
Explanation: Position 0 qualifies with zero required light, position 1 has its one lamp, and position 2 fails.
```
### Constraints
- `1 <= n <= 10^5`; `1 <= lights.length <= 10^5`.
- Lamp positions lie in `[0,n-1]`; ranges in `[0,10^5]`.
- `requirement.length == n`; each requirement lies in `[0,10^5]`.
### Clarifying Questions
Equality meets a requirement. Even an unlit position qualifies when its requirement is zero.
```hint Inspect the structure
How can each lamp update an entire inclusive interval using only two difference-array entries?
```
### Reasoning checkpoints
- Apply inclusive lamp coverage clipped to the street, counting overlapping lamps separately.
- Compare each position with its own required brightness, including equality and a zero requirement.
- Count qualifying positions rather than total brightness and support the full street and lamp bounds.
### Optional extensions
How would you answer many brightness queries when n is too large for a dense array?
Overview: Count Street Positions Meeting Their Light Requirement. The street consists of integer positions 0 through n-1. A lamp [position,range] lights every position in its inclusive interval, clipped to the street. requirement[i] is the minimum number of covering lamps needed at i. Return how many street positions have brightness at least their own requirement.
