Solution Explanation: Brightest Position on Street

This problem involves finding the position on a street with the maximum brightness, given the positions and ranges of street lamps. The brightness of a position is the number of lamps illuminating it.

The optimal approach leverages the concept of a difference array combined with a hash table (or map) for efficient computation.

Algorithm:

1. Difference Array Representation: Instead of directly calculating brightness for each position, which would be computationally expensive, we use a difference array. For each lamp at position position_i with range range_i, we consider the interval it illuminates: [position_i - range_i, position_i + range_i].

2. Updating the Difference Array: We represent this interval in the difference array as follows:

   • Add 1 to the count at position_i - range_i. This represents the start of the illuminated interval.
   • Subtract 1 from the count at position_i + range_i + 1. This represents the end of the illuminated interval. Adding 1 to the right boundary is crucial to correctly handle overlapping intervals.

3. Hash Table/Map: A hash table (or map in other languages) is used to efficiently store and access the difference array. The keys are the positions on the street, and the values represent the change in brightness at those positions.

4. Accumulating Brightness: We iterate through the sorted keys of the hash table (representing positions). We accumulate the changes in brightness to get the actual brightness at each position.

5. Finding the Brightest Position: During the iteration, we track the maximum brightness encountered and the corresponding position.

6. Return: The position with the maximum brightness is returned. If multiple positions have the same maximum brightness, the smallest one is returned.

Time Complexity: O(n log n), where n is the number of lamps. This is dominated by the sorting of the keys in the hash table. The other operations (iterating, updating the hash table) are linear in the number of lamps.

Space Complexity: O(n) in the worst case to store the hash table/map which in the worst case will store all the different position values.

Code Examples:

The code examples below demonstrate the solution in several programming languages. Note the use of a TreeMap in Java (to maintain sorted order), and equivalent sorted data structures in other languages to ensure correct processing of the difference array.

Python:

from collections import defaultdict
 
class Solution:
    def brightestPosition(self, lights: List[List[int]]) -> int:
        diff_array = defaultdict(int)
        for pos, range_ in lights:
            diff_array[pos - range_] += 1
            diff_array[pos + range_ + 1] -= 1
 
        sorted_positions = sorted(diff_array.keys())
        brightness = 0
        max_brightness = 0
        brightest_pos = 0
        current_pos = sorted_positions[0]
 
        for pos in sorted_positions:
            brightness += diff_array[pos]
            if brightness > max_brightness:
                max_brightness = brightness
                brightest_pos = current_pos
 
            current_pos = pos
        return brightest_pos

Java:

import java.util.*;
 
class Solution {
    public int brightestPosition(int[][] lights) {
        TreeMap<Integer, Integer> diffArray = new TreeMap<>();
        for (int[] light : lights) {
            int pos = light[0];
            int range = light[1];
            diffArray.put(pos - range, diffArray.getOrDefault(pos - range, 0) + 1);
            diffArray.put(pos + range + 1, diffArray.getOrDefault(pos + range + 1, 0) - 1);
        }
 
        int brightness = 0;
        int maxBrightness = 0;
        int brightestPos = 0;
        int currentPos = diffArray.firstKey();
 
        for (Map.Entry<Integer, Integer> entry : diffArray.entrySet()) {
            int pos = entry.getKey();
            int change = entry.getValue();
            brightness += change;
            if (brightness > maxBrightness) {
                maxBrightness = brightness;
                brightestPos = currentPos;
            }
            currentPos = pos;
        }
        return brightestPos;
    }
}

C++:

#include <map>
#include <algorithm>
 
class Solution {
public:
    int brightestPosition(vector<vector<int>>& lights) {
        map<int, int> diffArray;
        for (auto& light : lights) {
            int pos = light[0];
            int range = light[1];
            diffArray[pos - range]++;
            diffArray[pos + range + 1]--;
        }
 
        int brightness = 0;
        int maxBrightness = 0;
        int brightestPos = 0;
        int currentPos = diffArray.begin()->first;
 
        for (auto& entry : diffArray) {
            int pos = entry.first;
            int change = entry.second;
            brightness += change;
            if (brightness > maxBrightness) {
                maxBrightness = brightness;
                brightestPos = currentPos;
            }
            currentPos = pos;
        }
        return brightestPos;
    }
};

These code examples provide a clear and efficient solution to the "Brightest Position on Street" problem using a difference array and a sorted map. The use of a sorted map simplifies the process of calculating the brightness at each position. Remember that the specific implementation details (e.g., using defaultdict in Python or TreeMap in Java) are crucial for achieving the optimal time complexity.