Brightest Position on Street

medium array prefix sum

Problem

Each lamp[i] = [position, range] illuminates [position − range, position + range]. Return the smallest position with the maximum total brightness.

Inputlights = [[-3,2],[1,2],[3,3]]

Output-1

Brightness 3 is achieved first at position −1.

lights "p,r; p,r; ..."

def brightest_position(lights):
    events = {}
    for p, r in lights:
        events[p - r] = events.get(p - r, 0) + 1
        events[p + r + 1] = events.get(p + r + 1, 0) - 1
    cur = 0
    best = 0
    pos = 0
    for x in sorted(events):
        cur += events[x]
        if cur > best:
            best = cur
            pos = x
    return pos

function brightestPosition(lights) {
  const events = new Map();
  for (const [p, r] of lights) {
    events.set(p - r, (events.get(p - r) || 0) + 1);
    events.set(p + r + 1, (events.get(p + r + 1) || 0) - 1);
  }
  const keys = [...events.keys()].sort((a, b) => a - b);
  let cur = 0, best = 0, pos = 0;
  for (const x of keys) {
    cur += events.get(x);
    if (cur > best) { best = cur; pos = x; }
  }
  return pos;
}

class Solution {
    public int brightestPosition(int[][] lights) {
        TreeMap<Integer, Integer> events = new TreeMap<>();
        for (int[] l : lights) {
            events.merge(l[0] - l[1], 1, Integer::sum);
            events.merge(l[0] + l[1] + 1, -1, Integer::sum);
        }
        int cur = 0, best = 0, pos = 0;
        for (Map.Entry<Integer, Integer> e : events.entrySet()) {
            cur += e.getValue();
            if (cur > best) { best = cur; pos = e.getKey(); }
        }
        return pos;
    }
}

int brightestPosition(vector<vector<int>>& lights) {
    map<int, int> events;
    for (auto& l : lights) {
        events[l[0] - l[1]] += 1;
        events[l[0] + l[1] + 1] -= 1;
    }
    int cur = 0, best = 0, pos = 0;
    for (auto& e : events) {
        cur += e.second;
        if (cur > best) { best = cur; pos = e.first; }
    }
    return pos;
}

Explanation

Each lamp lights up a whole interval, and we want the position covered by the most lamps. Instead of touching every position in every interval, we use a difference / sweep-line trick: record only where coverage changes.

For a lamp covering [p - r, p + r], we add +1 at the start p - r and -1 just after the end, at p + r + 1. These are stored in an events map keyed by position.

Then we walk the event positions in sorted order, keeping a running brightness cur by adding each event's delta. Whenever cur beats the best so far, we record that position. Because we use a strict >, the smallest position that reaches the max is the one kept.

Example: lights = [[-3,2],[1,2],[3,3]]. The intervals overlap most around -1, where three lamps stack to brightness 3, and that is the first position reaching the maximum, so the answer is -1.

Sorting the event keys dominates the cost at O(n log n), and the sweep itself is linear.

Time: O(n log n) Space: O(n)