LeetCode 2021 - Brightest Position on Street

The problem asks us to find the position on a straight street that is illuminated by the largest number of street lamps, which is referred to as its brightness.

leetcodemediumarraysortingprefix-sumordered-set

LeetCode Problem 2021

Difficulty: 🟡 Medium
Topics: Array, Sorting, Prefix Sum, Ordered Set

Solution

Problem Understanding

The problem asks us to find the position on a straight street that is illuminated by the largest number of street lamps, which is referred to as its brightness. The street is represented as a number line, and each street lamp is given as a pair [positioni, rangei], which defines the interval [positioni - rangei, positioni + rangei] that the lamp illuminates, inclusive of both ends. The brightness of a position is simply the count of all lamps whose intervals cover that position. If multiple positions have the same maximum brightness, the smallest position should be returned.

The input is a 2D array of integers with up to 10^5 lamps, and the positions and ranges can be very large integers (up to 10^8 in magnitude). This makes a naive approach of checking every single integer on the number line infeasible. We must instead rely on an approach that does not explicitly iterate over every possible position.

Edge cases to consider include lamps with zero range (which illuminate only their exact position), overlapping ranges, negative positions, and the possibility that multiple positions share the same brightness. The input guarantees at least one lamp exists.

Approaches

A brute-force approach would iterate over the entire number line, for each position counting the number of lamps that cover it. This is correct in principle but infeasible because positions can range from -10^8 to 10^8, leading to an O(N * max_range) runtime, which is far too slow for the given constraints.

The optimal approach relies on the observation that brightness changes only at the start and end points of lamp intervals. If we treat the start of an interval as a +1 event and the position immediately after the end of an interval as a -1 event, we can sort all these events and simulate a running total of brightness. The maximum running total corresponds to the brightest position. This approach is efficient because it only considers positions where brightness changes, not every position on the number line.

Approach Time Complexity Space Complexity Notes
Brute Force O(N * R) O(1) Count brightness at every position in all lamp ranges; too slow for large ranges.
Optimal O(N log N) O(N) Use sweep line / prefix sum events at interval endpoints; efficient and scalable.

Algorithm Walkthrough

  1. Initialize an empty list events to store brightness changes.
  2. For each lamp [pos, rng], calculate the interval [start, end] = [pos - rng, pos + rng].
  3. For each interval, add two events: (start, +1) and (end + 1, -1). The +1 marks the start of illumination, and the -1 marks the first position after the illumination ends.
  4. Sort the events list by position. If multiple events occur at the same position, order does not matter because we will process them sequentially.
  5. Initialize current_brightness = 0 and max_brightness = 0. Also initialize brightest_position to a large sentinel value.
  6. Iterate through each (position, delta) in events:
  • Update current_brightness += delta.
  • If current_brightness > max_brightness, update max_brightness = current_brightness and set brightest_position = position.
  • If current_brightness == max_brightness, keep the smaller brightest_position.
  1. Return brightest_position.

Why it works: The algorithm works because brightness only changes at interval start and end points. By tracking these events in order, we accurately capture all transitions of brightness without checking every position, ensuring correctness and efficiency.

Python Solution

from typing import List

class Solution:
    def brightestPosition(self, lights: List[List[int]]) -> int:
        events = []
        for pos, rng in lights:
            start, end = pos - rng, pos + rng
            events.append((start, 1))
            events.append((end + 1, -1))
        
        events.sort()
        
        current_brightness = 0
        max_brightness = 0
        brightest_position = float('inf')
        
        for position, delta in events:
            current_brightness += delta
            if current_brightness > max_brightness:
                max_brightness = current_brightness
                brightest_position = position
            elif current_brightness == max_brightness:
                brightest_position = min(brightest_position, position)
        
        return brightest_position

This implementation first converts each lamp's range into a start and end event. Sorting the events ensures we process positions in order, and using a running total (current_brightness) allows us to efficiently track which position has the maximum number of overlapping lamps.

Go Solution

import "sort"

func brightestPosition(lights [][]int) int {
    type Event struct {
        pos   int
        delta int
    }
    
    events := make([]Event, 0, 2*len(lights))
    
    for _, lamp := range lights {
        start := lamp[0] - lamp[1]
        end := lamp[0] + lamp[1]
        events = append(events, Event{start, 1})
        events = append(events, Event{end + 1, -1})
    }
    
    sort.Slice(events, func(i, j int) bool {
        return events[i].pos < events[j].pos
    })
    
    currentBrightness := 0
    maxBrightness := 0
    brightestPosition := int(1e18)
    
    for _, e := range events {
        currentBrightness += e.delta
        if currentBrightness > maxBrightness {
            maxBrightness = currentBrightness
            brightestPosition = e.pos
        } else if currentBrightness == maxBrightness {
            if e.pos < brightestPosition {
                brightestPosition = e.pos
            }
        }
    }
    
    return brightestPosition
}

The Go version mirrors the Python approach. Go requires explicit struct types for events, and sorting is done via sort.Slice. A large sentinel value is used for brightestPosition to ensure correct comparison.

Worked Examples

Example 1: lights = [[-3,2],[1,2],[3,3]]

Event delta current_brightness max_brightness brightest_position
-5 +1 1 1 -5
-1 +1 2 2 -1
0 +1 3 3 0
4 -1 2 3 0
6 -1 1 3 0
7 -1 0 3 0

Brightest position is -1 (smallest among positions with brightness 2).

Example 2: lights = [[1,0],[0,1]]

Event delta current_brightness max_brightness brightest_position
-1 +1 1 1 -1
0 +1 2 2 0
1 +1 3 3 1
1 -1 2 3 1
2 -1 1 3 1

Brightest position is 1.

Example 3: lights = [[1,2]]

Event delta current_brightness max_brightness brightest_position
-1 +1 1 1 -1
4 -1 0 1 -1

Brightest position is -1.

Complexity Analysis

Measure Complexity Explanation
Time O(N log N) Sorting 2N events dominates runtime, iterating events is O(N).
Space O(N) We store two events per lamp.

The approach scales well to the constraints since sorting 2 * 10^5 events is feasible and avoids iterating over the huge number line.

Test Cases

sol = Solution()

# Provided examples
assert sol.brightestPosition([[-3,2],[1,2],[3,3]]) == -1  # Multiple overlapping intervals
assert sol.brightestPosition([[1,0],[0,1]]) == 1         # Smallest among brightest
assert sol.brightestPosition([[1,2]]) == -1              # Single lamp

# Edge cases
assert sol.brightestPosition([[0,0]]) == 0               # Single lamp at origin
assert sol.brightestPosition([[0,100000000],[100000000,0]]) == 0  # Very large ranges
assert sol.brightestPosition([[0,1],[2,1],[4,1]]) == -1  # Non-overlapping intervals
assert sol.brightestPosition([[0,1],[1,1],[2,