We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Brightest Position on Street

Number: 2075

Difficulty: Medium

Paid? Yes

Companies: Uber, Robinhood

Problem Description

A straight street is represented by a number line. Each street lamp is specified by its position and range, and it lights an interval on the street. The brightness at a given point is the number of street lamps that cover that point. Given an array of lamps where each lamp is defined as [position, range], find the position with the maximum brightness. If multiple positions have the same maximum brightness, return the smallest such position.

Key Insights

  • Each street lamp creates an interval [position - range, position + range] (inclusive).
  • Use a difference array or sweep-line technique by marking the start of an interval with +1 and the position right after the end with -1.
  • After sorting these events by coordinate, a single pass accumulates brightness and identifies the maximum brightness along with the smallest coordinate that attains it.
  • Handle gaps between events carefully since brightness is constant over these gaps.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting of the 2n events (n is the number of street lamps).
Space Complexity: O(n) for storing the events.

Solution

The problem is solved using a sweep-line (difference array) approach:

  1. For each street lamp, calculate the left bound (position - range) and the right bound (position + range).
  2. Create two events: add +1 at the left bound and add -1 at (right bound + 1) to account for the inclusiveness of the interval.
  3. Sort the events by their coordinate.
  4. Perform a sweep-line: as you traverse through the sorted events, accumulate the brightness. The brightness remains constant in the intervals between consecutive events.
  5. Track the maximum brightness seen so far and update the result with the smallest coordinate when a new maximum is found.
  6. Finally, return the coordinate corresponding to the maximum brightness.

Code Solutions

# Python solution using sweep-line technique
def brightestPosition(lights):
    events = []
    # Create events for each light: +1 at start, -1 at end+1 (because of inclusive interval)
    for pos, rng in lights:
        start = pos - rng
        end = pos + rng
        events.append((start, 1))
        events.append((end + 1, -1))
    
    # Sort events by coordinate value
    events.sort()
    
    max_brightness = 0
    current_brightness = 0
    brightest_position = float('inf')
    prev_position = None
    i = 0
    n = len(events)
    
    while i < n:
        current_position = events[i][0]
        # If we are transitioning from a previous coordinate, check constant segment
        if prev_position is not None and current_position != prev_position:
            # The brightness is constant in the interval [prev_position, current_position - 1]
            if current_brightness > max_brightness:
                max_brightness = current_brightness
                brightest_position = prev_position
            elif current_brightness == max_brightness:
                brightest_position = min(brightest_position, prev_position)
        
        # Process all events occurring at current_position
        while i < n and events[i][0] == current_position:
            current_brightness += events[i][1]
            i += 1
        
        prev_position = current_position
        
    return brightest_position

# Example usage:
print(brightestPosition([[-3,2],[1,2],[3,3]]))  # Expected output: -1
← Back to All Questions