Formatted question description: https://leetcode.ca/all/2021.html

# 2021. Brightest Position on Street (Medium)

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] = [position`

indicates that there is a street lamp at position _{i}, range_{i}]`position`

that lights up the area from _{i}`[position`

(_{i} - range_{i}, position_{i} + range_{i}]**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.

**Example 1:**

Input:lights = [[-3,2],[1,2],[3,3]]Output:-1Explanation:The first street lamp lights up the area from [(-3) - 2, (-3) + 2] = [-5, -1]. The second street lamp lights up the area from [1 - 2, 1 + 2] = [-1, 3]. The third street lamp lights up the area from [3 - 3, 3 + 3] = [0, 6]. Position -1 has a brightness of 2, illuminated by the first and second street light. Positions 0, 1, 2, and 3 have a brightness of 2, illuminated by the second and third street light. Out of all these positions, -1 is the smallest, so return it.

**Example 2:**

Input:lights = [[1,0],[0,1]]Output:1Explanation:The first street lamp lights up the area from [1 - 0, 1 + 0] = [1, 1]. The second street lamp lights up the area from [0 - 1, 0 + 1] = [-1, 1]. Position 1 has a brightness of 2, illuminated by the first and second street light. Return 1 because it is the brightest position on the street.

**Example 3:**

Input:lights = [[1,2]]Output:-1Explanation:The first street lamp lights up the area from [1 - 2, 1 + 2] = [-1, 3]. Positions -1, 0, 1, 2, and 3 have a brightness of 1, illuminated by the first street light. Out of all these positions, -1 is the smallest, so return it.

**Constraints:**

`1 <= lights.length <= 10`

^{5}`lights[i].length == 2`

`-10`

^{8}<= position_{i}<= 10^{8}`0 <= range`

_{i}<= 10^{8}

**Companies**:

Amazon

**Related Topics**:

Array, Prefix Sum, Ordered Set

**Similar Questions**:

## Solution 1. Heap

```
// OJ: https://leetcode.com/problems/brightest-position-on-street/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int brightestPosition(vector<vector<int>>& A) {
for (auto &v : A) {
int p = v[0], r = v[1];
v[0] = p - r;
v[1] = p + r;
}
sort(begin(A), end(A));
priority_queue<int, vector<int>, greater<>> pq;
int ans = INT_MIN, size = 0;
for (auto &v : A) {
int begin = v[0], end = v[1];
while (pq.size() && pq.top() < begin) pq.pop();
pq.push(end);
if (pq.size() > size) {
size = pq.size();
ans = begin;
}
}
return ans;
}
};
```

## Solution 2. Line Sweep

```
// OJ: https://leetcode.com/problems/brightest-position-on-street/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int brightestPosition(vector<vector<int>>& A) {
vector<int> begin, end;
for (auto &v : A) {
begin.push_back(v[0] - v[1]);
end.push_back(v[0] + v[1]);
}
sort(begin.begin(), begin.end());
sort(end.begin(), end.end());
int i = 0, j = 0, N = A.size(), ans = INT_MIN, size = 0;
for (; i < N; ++i) {
while (end[j] < begin[i]) ++j;
if (i - j + 1 > size) {
size = i - j + 1;
ans = begin[i];
}
}
return ans;
}
};
```

## Solution 3. Difference Array

```
// OJ: https://leetcode.com/problems/brightest-position-on-street/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int brightestPosition(vector<vector<int>>& A) {
map<int, int> m;
for (auto &v : A) {
m[v[0] - v[1]]++;
m[v[0] + v[1] + 1]--;
}
int size = 0, ans = INT_MIN, cnt = 0;
for (auto &[index, diff] : m) {
cnt += diff;
if (cnt > size) {
size = cnt;
ans = index;
}
}
return ans;
}
};
```