Find leftmost point of maximum brightness
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given an array of lights, where each light is [p, r] representing a lamp centered at coordinate p on the real number line with radius r, illuminating the closed interval [p − r, p + r]. The brightness at point x is the count of intervals that contain x. Return the smallest coordinate x with maximum brightness. If the maximum brightness occurs over an interval, return its left endpoint. Design an algorithm that runs in O(n log n) time without enumerating individual points on the number line, and explain your approach (e.g., event sweep or ordered map), tie-breaking, and correctness. Discuss how you would handle large coordinates (up to 1e
9), negative positions, and floating-point radii.
Quick Answer: This question evaluates understanding of interval overlap counting, efficient use of ordered data structures for range events, tie-breaking logic, and robustness to numeric edge cases such as large coordinates and floating-point radii.
You are given an array of lights, where each light is `[p, r]` representing a lamp centered at coordinate `p` on the real number line with radius `r`, illuminating the closed interval `[p - r, p + r]`. The brightness at a point `x` is the number of intervals that contain `x`. Return the smallest coordinate `x` with maximum brightness. If the maximum brightness occurs over a whole interval of coordinates, return that interval's left endpoint.
Solve it in O(n log n) time using an event sweep — without enumerating individual points on the number line (coordinates can be up to 1e9, positions can be negative). Because the lit intervals are closed, a `+1` (interval start) at a coordinate must take effect before any `-1` (interval end) at the same coordinate, so that two intervals merely touching at a shared endpoint are correctly counted as overlapping there.
Return `None` (null / empty) when the input is empty.
Constraints
- 0 <= n (number of lights)
- -1e9 <= p <= 1e9
- 0 <= r <= 1e9
- Intervals are closed: light [p, r] covers every x with p - r <= x <= p + r
- Two intervals that share only an endpoint coordinate DO overlap there
- Return the smallest coordinate achieving the maximum brightness; on an interval of maxima, return its left endpoint
- Return None / null for empty input
Examples
Input: ([[-2, 3], [1, 2]],)
Expected Output: -1
Explanation: Lamp [-2,3] lights [-5,1]; lamp [1,2] lights [-1,3]. They overlap on [-1,1] with brightness 2. The smallest such x is -1.
Input: ([[0, 1]],)
Expected Output: -1
Explanation: Single lamp lights [-1,1], brightness 1 everywhere on it. The leftmost point of the maximum is -1.
Hints
- Don't materialize the number line. Convert each lamp [p, r] into two events at coordinates p - r (start, +1) and p + r (end, -1).
- Sort events by coordinate. At ties, apply all starts (+1) before any ends (-1) so that intervals touching at a shared endpoint are counted as overlapping at that point.
- Sweep left to right tracking a running count. Each time the running count strictly exceeds the previous best, record the current coordinate as the answer — that coordinate is the left endpoint of the segment where the new maximum begins, which is exactly the smallest x with that brightness.
- Because you only update on a strict increase, the first (leftmost) coordinate that reaches the global maximum is returned automatically; later coordinates with equal brightness never overwrite it.