Brightest position on street

Array Sorting Prefix Sum Ordered Set

60.5% acceptance

Mar 31, 2026

172

A perfectly straight street is represented by a number line. The street has street lamp(s) on it and is represented by a 2D integer array lights. Each lights[i] = [positioni, rangei] indicates that there is a street lamp at position positioni that lights up the area from [positioni - rangei, positioni + rangei] (inclusive). The brightness of a position p is defined as the number of street lamp that light up the position p. Given lights, return the brightest position on the street. If there are multiple brightest positions, return the smallest one.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn brightest_position(lights: Vec<Vec<i32>>) -> i32 {
    // Sweep line with difference array on events
    let mut events: Vec<(i64, i32)> = Vec::new();
    for l in &lights {
      let pos = l[0] as i64;
      let range = l[1] as i64;
      events.push((pos - range, 1));
      events.push((pos + range + 1, -1));
    }
    events.sort();
    
    let mut brightness = 0;
    let mut max_brightness = 0;
    let mut result = 0i64;
    
    for &(pos, delta) in &events {
      brightness += delta;
      if brightness > max_brightness {
        max_brightness = brightness;
        result = pos;
      }
    }
    result as i32
  }
}