Problem Description

You are given a street represented as an infinite number line. There are n street lamps, each described by lights[i] = [positioni, rangei]. Each lamp lights up all positions from positioni - rangei to positioni + rangei (inclusive).

Your task is to find the brightest position on the street—that is, the position that is covered by the most lamps. If there are multiple such positions, return the smallest one.

Constraints:

• 1 ≤ n ≤ 105
• lights[i][0] and lights[i][1] are integers within reasonable bounds (e.g., -10⁹ to 10⁹)
• There is always at least one lamp
• There is always at least one position covered by at least one lamp

Thought Process

At first glance, one might consider simulating the entire number line and counting how many lamps cover each position. However, the number line is infinite, and even if we restrict ourselves to only the positions covered by lamps, the number of possible positions is huge (up to 2 × 10⁹).

Instead, we realize that the number of lamps covering a position only changes at the start or end of a lamp's range. So, rather than checking every position, we can focus on the points where coverage changes.

This leads us to a "sweep line" or "prefix sum" strategy, where we process only the events where lamps start and stop illuminating positions.

Solution Approach

We use an event-based sweep line algorithm:

1. For each lamp at positioni with rangei:
   • Add an event at positioni - rangei to increase coverage by 1 (lamp starts illuminating here).
   • Add an event at positioni + rangei + 1 to decrease coverage by 1 (lamp stops illuminating just after its end).
2. Collect all such events and sort them by position.
3. Sweep through the events in order:
   • Maintain a running total of the current coverage (number of lamps covering the current position).
   • Whenever the coverage increases to a new maximum, record the position.
   • If multiple positions have the same maximum coverage, keep the smallest one.
4. At the end, return the smallest position with the highest coverage.

This approach is efficient because it only processes 2n events, regardless of the size of the number line.

Example Walkthrough

Example: lights = [[2, 1], [4, 1], [6, 1]]

• Lamp 1: covers [1, 3]
• Lamp 2: covers [3, 5]
• Lamp 3: covers [5, 7]

We create events:

• At 1: +1 (lamp 1 starts)
• At 3: +1 (lamp 2 starts)
• At 3 + 1 = 4: -1 (lamp 1 ends)
• At 5: +1 (lamp 3 starts)
• At 5 + 1 = 6: -1 (lamp 2 ends)
• At 7 + 1 = 8: -1 (lamp 3 ends)

Sorting and sweeping:

• At 1: coverage=1 (max so far), brightest=1
• At 3: coverage=2 (max so far), brightest=3
• At 4: coverage=1
• At 5: coverage=2 (ties max, but 3 < 5, so brightest remains 3)
• At 6: coverage=1
• At 8: coverage=0

Code Implementation

class Solution:
    def brightestPosition(self, lights):
        events = []
        for pos, rng in lights:
            events.append((pos - rng, 1))
            events.append((pos + rng + 1, -1))
        events.sort()
        
        max_cover = 0
        curr_cover = 0
        brightest = None
        
        for pos, delta in events:
            curr_cover += delta
            if curr_cover > max_cover:
                max_cover = curr_cover
                brightest = pos
        return brightest
      

class Solution {
public:
    int brightestPosition(vector<vector<int>>& lights) {
        vector<pair<long long, int>> events;
        for (auto& lamp : lights) {
            long long pos = lamp[0], rng = lamp[1];
            events.emplace_back(pos - rng, 1);
            events.emplace_back(pos + rng + 1, -1);
        }
        sort(events.begin(), events.end());
        int maxCover = 0, currCover = 0;
        long long brightest = 0;
        for (auto& [pos, delta] : events) {
            currCover += delta;
            if (currCover > maxCover) {
                maxCover = currCover;
                brightest = pos;
            }
        }
        return static_cast<int>(brightest);
    }
};
      

import java.util.*;
class Solution {
    public int brightestPosition(int[][] lights) {
        List<long[]> events = new ArrayList<>();
        for (int[] lamp : lights) {
            long pos = lamp[0], rng = lamp[1];
            events.add(new long[]{pos - rng, 1});
            events.add(new long[]{pos + rng + 1, -1});
        }
        events.sort(Comparator.comparingLong(a -> a[0]));
        int maxCover = 0, currCover = 0;
        long brightest = 0;
        for (long[] event : events) {
            currCover += event[1];
            if (currCover > maxCover) {
                maxCover = currCover;
                brightest = event[0];
            }
        }
        return (int)brightest;
    }
}
      

var brightestPosition = function(lights) {
    let events = [];
    for (const [pos, rng] of lights) {
        events.push([pos - rng, 1]);
        events.push([pos + rng + 1, -1]);
    }
    events.sort((a, b) => a[0] - b[0]);
    let maxCover = 0, currCover = 0, brightest = null;
    for (const [pos, delta] of events) {
        currCover += delta;
        if (currCover > maxCover) {
            maxCover = currCover;
            brightest = pos;
        }
    }
    return brightest;
};
      

Time and Space Complexity

• Brute-force approach: If we checked every possible position, the time and space would be prohibitive (up to O(R), where R is the range of all covered positions, which can be up to 2 × 10⁹).
• Optimized sweep-line approach:
  • We create two events per lamp, so O(n) events.
  • Sorting the events takes O(n log n).
  • Sweeping through the events is O(n).
  • Total time complexity: O(n log n)
  • Space complexity: O(n) for the events array

This makes the solution efficient and scalable even for large inputs.

Summary

The key insight is that the number of lamps covering any position only changes at the start or end of a lamp's range. By focusing on these events, we can efficiently find the brightest position using a sweep-line algorithm, processing only O(n) events. This avoids the impracticality of simulating the entire number line and leads to a concise, elegant solution.