Brightest Position on Street - Practice Coding Problems

Brightest Position on Street - Problem

A perfectly straight street is represented by a number line. The street has street lamp(s) on it and is represented by a 2D integer array lights. Each lights[i] = [position_i, range_i] indicates that there is a street lamp at position position_i that lights up the area from [position_i - range_i, position_i + range_i] (inclusive).

The brightness of a position p is defined as the number of street lamps that light up the position p.

Given lights, return the brightest position on the street. If there are multiple brightest positions, return the smallest one.

Input & Output

Example 1 — Basic Two Lamps

$ Input: lights = [[1,1],[3,2]]

› Output: 1

💡 Note: Lamp 1 at position 1 with range 1 covers [0,2]. Lamp 2 at position 3 with range 2 covers [1,5]. Position 1 and 2 both have brightness 2, but we return the smaller position 1.

Example 2 — Single Lamp

$ Input: lights = [[2,3]]

› Output: -1

💡 Note: Single lamp at position 2 with range 3 covers [-1,5]. All positions have brightness 1, so return the smallest position -1.

Example 3 — Multiple Overlaps

$ Input: lights = [[1,0],[0,1]]

› Output: 0

💡 Note: Lamp 1 at position 1 with range 0 covers [1,1]. Lamp 2 at position 0 with range 1 covers [-1,1]. Position 0 and 1 both have brightness 1, return smaller position 0.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Street lamps with position and range

Coverage

Each lamp illuminates an area around its position

Brightness

Count overlapping lamps at each position

Key Takeaway

🎯 Key Insight: Use line sweep with difference array to efficiently track brightness changes at critical positions

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use coordinate compression with a difference array to efficiently track brightness changes. Instead of checking every position, we only process critical points where brightness changes. Best approach uses line sweep technique. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Positions	O(R × n)	O(1)	Check every position in the range and count overlapping lamps
Difference Array (Line Sweep)	O(n log n)	O(n)	Use difference array to efficiently track brightness changes

Brute Force - Check All Positions — Algorithm Steps

Find the range of all possible positions
For each position, count overlapping lamp ranges
Track maximum brightness and smallest position

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Range

Determine min and max possible positions

Check Each Position

Count how many lamps illuminate each position

Find Maximum

Return position with highest brightness

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int lights[][2], int n) {
    if (n == 0) return 0;
    
    // Find the range of all positions
    int minPos = INT_MAX;
    int maxPos = INT_MIN;
    
    for (int i = 0; i < n; i++) {
        int start = lights[i][0] - lights[i][1];
        int end = lights[i][0] + lights[i][1];
        if (start < minPos) minPos = start;
        if (end > maxPos) maxPos = end;
    }
    
    int maxBrightness = 0;
    int brightestPos = minPos;
    
    // Check each position in range
    for (int pos = minPos; pos <= maxPos; pos++) {
        int brightness = 0;
        for (int i = 0; i < n; i++) {
            if (lights[i][0] - lights[i][1] <= pos && pos <= lights[i][0] + lights[i][1]) {
                brightness++;
            }
        }
        
        if (brightness > maxBrightness) {
            maxBrightness = brightness;
            brightestPos = pos;
        }
    }
    
    return brightestPos;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[a,b],[c,d],...] format
    int lights[1000][2];
    int n = 0;
    
    char *ptr = line + 1; // Skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            lights[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            lights[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            n++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(lights, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(R × n)

R is the range of positions (can be very large), n is number of lamps

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track maximum brightness and position

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Positions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler