2021. Brightest Position on Street - Detailed Explanation

Problem Statement

You are given a list of street lamps where each lamp is described by three integers:
• position – the location of the lamp on the street (an integer coordinate),
• range – the distance to both sides from the lamp within which it illuminates, and
• brightness – the amount of brightness the lamp contributes to every position it illuminates.

Each lamp illuminates every integer position in the interval ([position - range,, position + range]) (inclusive). The total brightness at any given position is the sum of the brightness values from all lamps that cover that position. Your task is to determine the position on the street that has the maximum total brightness. If there are multiple positions with the same maximum brightness, return the smallest such position.

Example 1

• Input: lamps = ([[2, 3, 4], [3, 1, 3]])
• Output: 2
• Explanation:
  • Lamp 1 is at position 2, has range 3, and brightness 4. It illuminates positions from (-1) to 5.
  • Lamp 2 is at position 3, has range 1, and brightness 3. It illuminates positions from 2 to 4.
  • At positions 2, 3, and 4, the total brightness is (4 + 3 = 7).
  • The brightest positions are 2, 3, and 4, but the smallest is 2.

Example 2

• Input: lamps = ([[5, 2, 10]])
• Output: 3
• Explanation:
  • The single lamp at position 5 with range 2 illuminates positions from 3 to 7, each receiving a brightness of 10.
  • The brightest brightness is 10 at all these positions; hence the smallest position is 3.

Constraints:
• The number of lamps can be large.
• The range of positions may be large, so an efficient algorithm is required to avoid scanning every possible position explicitly.

Hints

1. Difference Array / Sweep Line Technique:
   Rather than checking every position individually, use a difference array (or a map for sparse ranges) to record changes in brightness. For each lamp, add its brightness to the starting position of its effect and subtract it from the position immediately after the end of its effect.

2. Prefix Sum to Calculate Brightness:
   After processing all lamps with the difference array technique, perform a prefix sum over the affected range of positions. This will yield the total brightness at each position.

3. Tracking Maximum Brightness:
   While computing the prefix sum, keep track of the maximum brightness encountered and note the smallest position where this maximum occurs.

Approaches

Brute Force Approach

• Idea:
  For every integer position that is illuminated by at least one lamp, sum the brightness contributions from each lamp.
• Drawback:
  This approach is very inefficient because it may require iterating over a huge range of positions and processing every lamp for each position.

Optimal Approach: Difference Array with Prefix Sum

• Idea:
  Use the difference array technique to mark where brightness contributions begin and end, then compute the prefix sum to get the brightness at each position.
• Steps:
  1. Determine the Range:
     Find the minimum and maximum positions affected by any lamp. For each lamp with ([position, range, brightness]), the lamp affects positions from (position - range) to (position + range).
  2. Apply the Difference Array Technique:
     For each lamp, do the following:
     • Add the lamp’s brightness at (start = position - range).
     • Subtract the lamp’s brightness at (end + 1 = position + range + 1).
  3. Compute the Prefix Sum:
     Iterate through the positions in the affected range. At each position, add the difference value from the previous position to determine the current total brightness.
  4. Find the Brightest Position:
     Track the maximum brightness value and update the result if a new maximum is found. If multiple positions share the same maximum brightness, choose the smallest position.

Complexity Analysis

• Time Complexity:
  Let (m) be the number of lamps and (L) be the length of the affected range (which may be optimized using a sorted map if the range is sparse).
  • Processing lamps takes (O(m)).
  • Building the prefix sum over (L) positions takes (O(L)).
• Space Complexity:
  • Using a difference array (or a hash map for sparse ranges) requires (O(L)) space in the worst case.