Brightest Position on Street

Medium

Robinhood

2 views

Topics:

ArraysTwo PointersSliding Windows

There is a street represented as a number line. You are given 2D integer array lights where lights[i] = [position_i, range_i] indicates that there is a light at position position_i that lights the area from position_i - range_i to position_i + range_i (inclusive).

You want to find the brightest position on the street. A position on the street is bright if the number of lights that light up the position is the greatest.

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: -1
Explanation:
The first light lights the area from -3 - 2 = -5 to -3 + 2 = -1.
The second light lights the area from 1 - 2 = -1 to 1 + 2 = 3.
The third light lights the area from 3 - 3 = 0 to 3 + 3 = 6.
The position -1 has the greatest number of lights shining on it, which is 2.

Example 2:

Input: lights = [[1,0],[0,1]]
Output: 1
Explanation:
The first light lights the area from 1 - 0 = 1 to 1 + 0 = 1.
The second light lights the area from 0 - 1 = -1 to 0 + 1 = 1.
The position 1 has the greatest number of lights shining on it, which is 2.

Constraints:

1 <= lights.length <= 10⁵
lights[i].length == 2
-10⁸ <= position_i <= 10⁸
0 <= range_i <= 10⁸

Try coding it in LeetCode

Brightest Position on Street

Medium

Robinhood

2 views

Topics:

ArraysTwo PointersSliding Windows

There is a street represented as a number line. You are given 2D integer array lights where lights[i] = [position_i, range_i] indicates that there is a light at position position_i that lights the area from position_i - range_i to position_i + range_i (inclusive).

You want to find the brightest position on the street. A position on the street is bright if the number of lights that light up the position is the greatest.

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: -1
Explanation:
The first light lights the area from -3 - 2 = -5 to -3 + 2 = -1.
The second light lights the area from 1 - 2 = -1 to 1 + 2 = 3.
The third light lights the area from 3 - 3 = 0 to 3 + 3 = 6.
The position -1 has the greatest number of lights shining on it, which is 2.

Example 2:

Input: lights = [[1,0],[0,1]]
Output: 1
Explanation:
The first light lights the area from 1 - 0 = 1 to 1 + 0 = 1.
The second light lights the area from 0 - 1 = -1 to 0 + 1 = 1.
The position 1 has the greatest number of lights shining on it, which is 2.

Constraints:

1 <= lights.length <= 10⁵
lights[i].length == 2
-10⁸ <= position_i <= 10⁸
0 <= range_i <= 10⁸

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the `positions` and `strengths` values? Can they be negative, zero, or very large?
Could the input arrays `positions` and `strengths` be empty or null? If so, what should I return?
Is the `k` value always a non-negative integer?
If multiple positions have the same maximum brightness, which position should I return? (e.g., the first one encountered, the smallest position value, etc.)?
Are the `positions` array guaranteed to be sorted, or will I need to sort it myself to optimize the calculation of brightness?

Brute Force Solution

Approach

To find the brightest spot on a street using a brute-force method, imagine walking down the street and, for every single position, checking the brightness caused by all the lights. We calculate the total brightness for each possible position on the street.

Here's how the algorithm would work step-by-step:

Consider each point on the street one by one as a potential location.
For each of these locations, go through every light on the street.
If a light's influence reaches the location you are considering, add the light's brightness to a total brightness value for that location.
Keep track of the total brightness for each location on the street.
After checking every location, find the location with the highest total brightness value. This is the brightest spot.

Code Implementation

def brightest_position_brute_force(lights):
    max_position = -1
    max_brightness = 0

    # Iterate through all possible positions
    for current_position in range(1, 101): 

        total_brightness = 0

        # Iterate through all lights to calculate total brightness at position
        for light_position, light_range, light_brightness in lights:
            if current_position >= light_position - light_range and \
               current_position <= light_position + light_range:

                total_brightness += light_brightness

        # Find the position with the maximum brightness
        if total_brightness > max_brightness:
            # Update the max brightness and position
            max_brightness = total_brightness
            max_position = current_position

    return max_position

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the number of potential locations on the street and m be the number of lights. For each location, we iterate through all the lights to determine its brightness contribution. This means that for every one of the n locations, we perform m operations (checking each light). Therefore, the total number of operations is proportional to n multiplied by m, giving a time complexity of O(n*m).

Space Complexity

O(1) – The provided algorithm calculates the brightness for each point on the street and keeps track of the maximum brightness encountered so far. It only requires a few variables to store the current position, the total brightness at that position, and the maximum brightness found. Since the number of variables used does not depend on the number of lights or the length of the street (denoted as N), the auxiliary space remains constant. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The core idea is to treat each house's location and brightness as key moments where the total brightness on the street changes. We'll efficiently track how the overall brightness increases and decreases at these locations to find the point with the maximum brightness. We accomplish this without individually checking every house or position.

Here's how the algorithm would work step-by-step:

Imagine each house's location as a point on a line. When you reach a house, the street's brightness increases by that house's brightness.
Also, the brightness from that house is only present from that location to the end of its reach. This means when you pass the end of its reach, the brightness should decrease.
Think of each house as adding a 'brightness contribution' at its location and removing that contribution at the end of its range.
Sort all these 'brightness contribution' and 'brightness removal' points by their locations on the line.
Go through these sorted points one by one, and keep a running total of the street's brightness. Increase the total when you hit a 'contribution' point and decrease it at a 'removal' point.
While doing this, keep track of the highest brightness total you've seen and the location where you saw it.
In the end, the location where you saw the highest brightness total is the brightest position on the street.

Code Implementation

def brightest_position(lights):
    brightness_changes = []
    for position, range_value, brightness in lights:
        brightness_changes.append((position, brightness))
        brightness_changes.append((position + range_value, -brightness))

    # Sorting ensures events are processed in the correct order.
    brightness_changes.sort()

    current_brightness = 0
    max_brightness = 0
    brightest_position_so_far = 0

    for position, brightness_change in brightness_changes:
        current_brightness += brightness_change

        # Keep track of the position with the maximum brightness seen so far
        if current_brightness > max_brightness:
            max_brightness = current_brightness
            brightest_position_so_far = position

    # Return the position with the highest brightness
    return brightest_position_so_far

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm's time complexity is primarily determined by sorting the brightness contribution and removal points. We have n houses, each generating two points (start and end of reach), resulting in 2n points to sort. Sorting these 2n points using an efficient algorithm like merge sort or quicksort takes O(n log n) time. The subsequent linear scan to calculate the maximum brightness and its location takes O(n) time. Since O(n log n) dominates O(n), the overall time complexity is O(n log n).

Space Complexity

O(N) – The algorithm creates a list of brightness contribution and removal points. Each house contributes two points to this list, one for the start of its range and one for the end. Therefore, the size of this list grows linearly with the number of houses, N. Sorting this list also contributes O(N) space in some sorting algorithms if not done in-place. Thus the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty positions or strengths array	Return -1 or throw an exception as there are no lights to consider.
positions and strengths arrays have different lengths	Return -1 or throw an IllegalArgumentException to signal an invalid input.
k is zero	The brightness at any position is just the strength of the light at that position, so return the position with the max strength.
All positions are the same	The position with the maximum strength among the duplicated ones is the result.
All strengths are the same	The position among the positions with the smallest values is the desired result.
positions are very large numbers, potentially causing integer overflow during calculation of p - k and p + k	Use long data type for intermediate calculations to prevent potential overflow issues.
Large input size (N positions), causing performance issues	Optimize the brightness calculation using a prefix sum or sliding window approach for better time complexity.
Negative values in positions and/or strengths	The solution should correctly handle negative positions and strengths as the brightness can be negative or the positions may be on the negative side of the number line.