⚡Flashcard Drill➔
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

  1. This is a sweep-line problem: each lamp contributes +1 at position - range and -1 at position + range + 1.
  2. Sort the event positions and accumulate the running brightness.
  3. Track the maximum brightness and the position where it first occurs.
  4. 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 + r instead of pos + 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems