Problem Description

You have a straight street represented as a number line with street lamps placed at various positions. Each street lamp is described by two values: its position on the number line and its range (how far its light reaches).

Given a 2D array lights where each element lights[i] = [position_i, range_i]:

• position_i is where the street lamp is located
• range_i is how far the light extends in both directions
• The lamp illuminates the area from [position_i - range_i, position_i + range_i] (inclusive)

The brightness at any position on the street is defined as the number of street lamps that illuminate that position. Multiple lamps can overlap and illuminate the same area, making it brighter.

Your task is to find the position on the street with the maximum brightness. If multiple positions have the same maximum brightness, return the smallest position.

For example, if a lamp is at position 5 with range 3, it illuminates positions [2, 3, 4, 5, 6, 7, 8]. If another lamp at position 7 with range 2 illuminates [5, 6, 7, 8, 9], then positions 5, 6, 7, 8 would have brightness 2 (illuminated by both lamps), while other positions would have brightness 1 or 0.

Intuition

The naive approach would be to check every possible position on the street and count how many lamps illuminate it. However, this could be inefficient if the range of positions is large.

Instead, we can observe that the brightness only changes at specific points - when we enter or exit the range of a lamp. Between these critical points, the brightness remains constant.

Think of it like this: when we walk along the street from left to right, the brightness increases by 1 when we enter a lamp's illuminated area (at position position_i - range_i), and decreases by 1 when we exit it (just after position position_i + range_i).

This observation leads us to use a difference array technique. Rather than tracking the brightness at every single position, we only track the changes in brightness:

• Mark +1 at the start of each lamp's range
• Mark -1 at the position right after the end of each lamp's range

By accumulating these changes as we scan from left to right, we can reconstruct the actual brightness at any position. Since we only need to process positions where changes occur, we use a hash table to store these change points efficiently.

After collecting all the change points, we sort them by position and traverse from left to right, maintaining a running sum of brightness. Whenever we encounter a new maximum brightness, we record that position. Since we're traversing in ascending order, we automatically get the smallest position when there are ties.

Learn more about Prefix Sum and Sorting patterns.

Solution Approach

The solution implements the difference array technique using a hash table and sorting:

Step 1: Build the Difference Array

We use a defaultdict(int) to store the brightness changes at specific positions. For each lamp at [position_i, range_i]:

• Calculate the left boundary: l = position_i - range_i
• Calculate the right boundary: r = position_i + range_i
• Mark +1 at position l (entering the illuminated area)
• Mark -1 at position r + 1 (exiting the illuminated area)

d = defaultdict(int)
for i, j in lights:
    l, r = i - j, i + j
    d[l] += 1
    d[r + 1] -= 1

Step 2: Process Positions in Sorted Order

We sort the positions where changes occur and traverse them from left to right:

• Initialize variables: ans = 0 (answer position), s = 0 (current brightness), mx = 0 (maximum brightness)
• For each position k in sorted order:
  • Add the change value to the running sum: s += d[k]
  • If current brightness s exceeds the maximum mx:
    • Update maximum: mx = s
    • Record this position as the answer: ans = k

ans = s = mx = 0
for k in sorted(d):
    s += d[k]
    if mx < s:
        mx = s
        ans = k

Why This Works:

1. The hash table ensures we only process positions where brightness changes, making the solution efficient even for large coordinate ranges
2. Sorting the positions ensures we check them in ascending order, automatically giving us the smallest position when there are ties
3. The running sum s accurately tracks the brightness at each change point because we've recorded all entries and exits from lamp ranges

Time Complexity: O(n log n) where n is the number of lamps, due to sorting the change points.

Space Complexity: O(n) for storing the difference array in the hash table.

Example Walkthrough

Let's walk through a concrete example with lights = [[5, 3], [7, 2]].

Step 1: Understanding the lamp coverage

• Lamp 1 at position 5 with range 3 illuminates [2, 3, 4, 5, 6, 7, 8]
• Lamp 2 at position 7 with range 2 illuminates [5, 6, 7, 8, 9]

Step 2: Build the difference array

For lamp [5, 3]:

• Left boundary: 5 - 3 = 2
• Right boundary: 5 + 3 = 8
• Mark +1 at position 2 (start of illumination)
• Mark -1 at position 9 (8 + 1, end of illumination)

For lamp [7, 2]:

• Left boundary: 7 - 2 = 5
• Right boundary: 7 + 2 = 9
• Mark +1 at position 5 (start of illumination)
• Mark -1 at position 10 (9 + 1, end of illumination)

Our difference array d becomes:

d = {2: 1, 9: -1, 5: 1, 10: -1}

Step 3: Process positions in sorted order

Sort the positions: [2, 5, 9, 10]

Now traverse and accumulate:

Result: The maximum brightness is 2, occurring at position 5.

Verification:

• Positions 2, 3, 4: brightness = 1 (only lamp 1)
• Positions 5, 6, 7, 8: brightness = 2 (both lamps)
• Position 9: brightness = 1 (only lamp 2)
• Other positions: brightness = 0

The answer is position 5, which is the smallest position with maximum brightness of 2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The algorithm iterates through the lights array once to create interval boundaries, which takes O(n) time. Each light creates two boundary points (start and end), resulting in at most 2n entries in the dictionary d. The dominant operation is sorting these boundary points using sorted(d), which has a time complexity of O(2n × log(2n)) = O(n × log n). The final iteration through the sorted keys takes O(2n) = O(n) time. Therefore, the overall time complexity is O(n) + O(n × log n) + O(n) = O(n × log n).

Space Complexity: O(n)

The algorithm uses a dictionary d to store the boundary points. In the worst case, each light contributes two unique boundary points (left and right + 1), resulting in at most 2n entries in the dictionary, which requires O(2n) = O(n) space. The sorted operation creates a list of keys which also takes O(n) space. Additional variables (ans, s, mx) use constant space O(1). Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow with Large Coordinates

When calculating boundaries (position - range or position + range), the result might exceed typical integer bounds if positions and ranges are very large.

Example Problem:

• Light at position 10^9 with range 10^9 would create a right boundary of 2 * 10^9

Solution:

• In Python, integers have arbitrary precision, so this isn't an issue
• In languages like Java/C++, use long data type or check for overflow conditions

2. Forgetting the +1 Offset for Range End

A critical mistake is marking the range end at position + range instead of position + range + 1.

Incorrect Code:

d[r] -= 1  # Wrong! This would exclude the last position

Correct Code:

d[r + 1] -= 1  # Correct: decrement happens AFTER the range ends

Why it matters: The range is inclusive of both endpoints. If we decrement at position r, we'd incorrectly reduce brightness at the last illuminated position.

3. Not Handling Empty Input

If the lights array is empty, the code would return 0 as the brightest position, which might not be the intended behavior.

Solution:

def brightestPosition(self, lights: List[List[int]]) -> int:
    if not lights:
        return 0  # or raise an exception based on requirements
  
    # rest of the code...

4. Misunderstanding the Tie-Breaking Rule

When multiple positions have the same maximum brightness, returning the wrong position is a common error.

Incorrect Approach:

if current_brightness >= max_brightness:  # Wrong! This returns the LAST position with max brightness
    max_brightness = current_brightness
    brightest_position = position

Correct Approach:

if current_brightness > max_brightness:  # Correct: Only update on strictly greater brightness
    max_brightness = current_brightness
    brightest_position = position

5. Processing Positions in Wrong Order

Using an unordered iteration over the dictionary keys would give incorrect results.

Incorrect:

for position in brightness_changes:  # Wrong! Dictionary iteration order isn't guaranteed to be sorted
    current_brightness += brightness_changes[position]

Correct:

for position in sorted(brightness_changes):  # Correct: Must process in ascending order
    current_brightness += brightness_changes[position]

6. Confusion Between Position and Index

The problem deals with positions on a number line, not array indices. Positions can be negative or non-consecutive.

Example: Lights at positions [-5, 3] and [100, 2] are valid inputs. Don't assume positions start at 0 or are consecutive integers.