NeetCode #160LC-2021MediumArrays & Hashing
← Back to All Problems#160 · #2021 · Brightest Position on Street(街上最亮的位置)
📌 Problem Statement & Constraints
There is a street with positions on a number line. Each
lights[i] = [position, range] describes a lamp that illuminates the closed interval [position - range, position + range]. Return the brightest position; on ties, return the smallest such position. Constraints: 1 <= lights.length <= 10^5, -10^8 <= position, range <= 10^8.💡 Core Algorithmic Approaches
- This is a sweep-line problem: each lamp contributes
+1atposition - rangeand-1atposition + range + 1. - Sort the event positions and accumulate the running brightness.
- Track the maximum brightness and the position where it first occurs.
- Iterating events in ascending order and using a strict
>comparison naturally yields the smallest position on ties.
💻 Benchmark Python3 Implementation
class Solution:
def brightestPosition(self, lights: List[List[int]]) -> int:
from collections import defaultdict
events = defaultdict(int)
for pos, r in lights:
events[pos - r] += 1 # illumination starts
events[pos + r + 1] -= 1 # illumination ends (exclusive upper bound)
cur = 0
best = 0
res = 0
for x in sorted(events):
cur += events[x]
if cur > best: # strict '>' keeps the smallest position
best = cur
res = x
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): building the events is O(n) and sorting them is O(n log n).
💾 Space Complexity
O(n) for the event map.
⚠️ Interview Pitfalls & Follow-ups
- Expanding each lamp's interval explicitly: the ranges can be up to 10^8 wide, so the sweep line is required.
- Decrementing at
pos + rinstead ofpos + r + 1: the interval is closed, so the illumination ends one position after the last lit cell. - Using
>=when updating the best: that would keep the largest position on ties, but the problem asks for the smallest. - Handling negative positions incorrectly: the constraints allow negative positions, and the sweep line handles them without special cases.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.