Count Positions on Street With Required Brightness

Count Positions on Street With Required Brightness

What is this problem about?

The "Count Positions on Street With Required Brightness interview question" is a 1D range update problem. You are given a set of street lamps, each defined by its position and range. A lamp at position $p$ with range $r$ provides brightness to all integer positions in the segment $[p-r, p+r]$. You are also given a requirement array where requirement[i] is the minimum brightness needed at position $i$. Your task is to count how many positions meet or exceed their brightness requirement.

Why is this asked in interviews?

Google ask the "Count Positions on Street With Required Brightness coding problem" to test a candidate's ability to handle multiple range updates efficiently. A brute-force approach of updating every index for every lamp is $O(N^2)$. The preferred solution uses the "Prefix Sum interview pattern" or "Difference Array" to achieve $O(N)$ time.

Algorithmic pattern used

This problem utilizes the Difference Array and Prefix Sum pattern.

1. Difference Array: Initialize an array diff of size $n+1$. For each lamp $[p, r]$:
   • Calculate the start and end of the lit range: start = max(0, p-r), end = min(n-1, p+r).
   • Increment diff[start] by 1.
   • Decrement diff[end+1] by 1.
2. Brightness Calculation: Iterate through the street and compute the prefix sum of diff. The prefix sum at index i is the total brightness at that position.
3. Validation: Compare the calculated brightness at each index i with requirement[i]. Increment the result counter if the brightness is sufficient.

Example explanation

Street length $n=3$, Lamps: [[0, 1]], Requirement: [1, 1, 0]

1. Lamp [0, 1] covers $[0-1, 0+1]$, clipped to $[0, 1]$.
2. diff array: diff[0]=1, diff[2]=-1.
3. Prefix sums:
   • index 0: 1. (Req 1: OK)
   • index 1: $1+0=1$. (Req 1: OK)
   • index 2: $1+0-1=0$. (Req 0: OK) Total OK positions: 3.

Common mistakes candidates make

• Simulation Inefficiency: Using a loop to increment every position in a lamp's range, leading to $O(L \cdot N)$ complexity.
• Boundary Clipping: Forgetting to use max(0, ...) and min(n-1, ...) when calculating the start and end of the light segment.
• Difference Array Size: Failing to make the difference array one element larger than the street to avoid index out of bounds when decrementing at end+1.

Interview preparation tip

Master the "Difference Array" technique! It is the standard way to perform multiple range additions in $O(1)$ time per update. It's an essential tool for "Array interview pattern" problems involving interval coverage.