Count Positions on Street With Required Brightness

Count Positions on Street With Required Brightness - Problem

You are given an integer n. A perfectly straight street is represented by a number line ranging from 0 to n - 1.

You are given a 2D integer array lights representing the street lamps on the street. Each lights[i] = [position_i, range_i] indicates that there is a street lamp at position position_i that lights up the area from [max(0, position_i - range_i), min(n - 1, 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.

You are given a 0-indexed integer array requirement of size n where requirement[i] is the minimum brightness of the i^th position on the street.

Return the number of positions i on the street between 0 and n - 1 that have a brightness of at least requirement[i].

Input & Output

Example 1 — Basic Case

$ Input: n = 5, lights = [[0,1],[2,1],[3,2]], requirement = [2,2,2,2,2]

› Output: 2

💡 Note: Position 0: covered by lamp [0,1] → brightness = 1 < 2. Position 1: covered by lamps [0,1] and [2,1] → brightness = 2 ≥ 2. Position 2: covered by lamps [2,1] and [3,2] → brightness = 2 ≥ 2. Position 3: covered by lamps [2,1] and [3,2] → brightness = 2 ≥ 2. Position 4: covered by lamp [3,2] → brightness = 1 < 2. Only positions 1 and 3 meet requirements.

Example 2 — All Satisfied

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

› Output: 3

💡 Note: Single lamp at position 1 with range 2 covers positions [max(0,1-2), min(3-1,1+2)] = [0,2]. All positions have brightness = 1 ≥ 1.

Example 3 — High Requirements

$ Input: n = 4, lights = [[0,1],[1,1]], requirement = [1,2,1,1]

› Output: 3

💡 Note: Lamp [0,1] covers [0,1]. Lamp [1,1] covers [0,2]. Position 0: brightness = 2 ≥ 1. Position 1: brightness = 2 ≥ 2. Position 2: brightness = 1 ≥ 1. Position 3: brightness = 0 < 1. Three positions satisfy requirements.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ lights.length ≤ 10⁵
0 ≤ position_i < n
0 ≤ range_i ≤ 10⁵
requirement.length == n
0 ≤ requirement[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Street positions 0 to n-1, lamps with position and range

Coverage

Each lamp illuminates a range of positions

Count

Count positions where brightness ≥ requirement

Key Takeaway

🎯 Key Insight: Use difference array to efficiently calculate brightness at all positions with range updates

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use a difference array for efficient range updates. Instead of checking each position individually, we mark lamp coverage ranges with +1 at start and -1 at end+1. Then calculate prefix sum to get brightness at all positions in O(n+m) time. Best approach is difference array. Time: O(n+m), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Difference Array (Range Updates)	O(n + m)	O(n)	Use difference array to efficiently handle range updates from lamps
Brute Force	O(n × m)	O(1)	For each position, count all lamps that illuminate it

Difference Array (Range Updates) — Algorithm Steps

Create difference array of size n+1
For each lamp, mark range start (+1) and end+1 (-1)
Calculate prefix sum to get brightness at each position
Compare brightness with requirements

Visualization

Tap to expand

Step-by-Step Walkthrough

Mark Ranges

Add +1 at start, -1 at end+1 of each lamp range

Prefix Sum

Calculate running sum to get brightness at each position

Compare

Check brightness vs requirements

Code -

solution.c — C

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

int solution(int n, int lights[][2], int lightsSize, int* requirement) {
    // Create difference array
    int* diff = (int*)calloc(n + 1, sizeof(int));
    
    // Mark lamp coverage ranges
    for (int i = 0; i < lightsSize; i++) {
        int lampPos = lights[i][0];
        int lampRange = lights[i][1];
        int left = (0 > lampPos - lampRange) ? 0 : lampPos - lampRange;
        int right = (n - 1 < lampPos + lampRange) ? n - 1 : lampPos + lampRange;
        diff[left] += 1;
        diff[right + 1] -= 1;
    }
    
    // Calculate brightness using prefix sum
    int brightness = 0;
    int result = 0;
    for (int i = 0; i < n; i++) {
        brightness += diff[i];
        if (brightness >= requirement[i]) {
            result++;
        }
    }
    
    free(diff);
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char lightsStr[10000];
    scanf(" %s", lightsStr);
    
    // Simple parsing for lights array
    int lights[1000][2];
    int lightsSize = 0;
    char* ptr = lightsStr + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            lights[lightsSize][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            lights[lightsSize][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            lightsSize++;
        }
        ptr++;
    }
    
    char reqStr[10000];
    scanf(" %s", reqStr);
    
    int requirement[1000];
    int reqSize = 0;
    ptr = reqStr + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr >= '0' && *ptr <= '9') {
            requirement[reqSize] = atoi(ptr);
            reqSize++;
            while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
        } else {
            ptr++;
        }
    }
    
    int result = solution(n, lights, lightsSize, requirement);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Process m lamps once, then calculate n prefix sums

✓ Linear Growth

Space Complexity

O(n)

Difference array of size n

⚡ Linearithmic 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

Difference Array (Range Updates) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler