K Empty Slots - Practice Coding Problems

K Empty Slots - Problem

Array Binary Indexed Tree Segment Tree Queue Sliding Window Heap (Priority Queue) Ordered Set Monotonic Queue Hard

You have n bulbs in a row numbered from 1 to n. Initially, all the bulbs are turned off. We turn on exactly one bulb every day until all bulbs are on after n days.

You are given an array bulbs of length n where bulbs[i] = x means that on the (i+1)th day, we will turn on the bulb at position x where i is 0-indexed and x is 1-indexed.

Given an integer k, return the minimum day number such that there exists two turned on bulbs that have exactly k bulbs between them that are all turned off. If there isn't such day, return -1.

Input & Output

Example 1 — Basic Case

$ Input: bulbs = [1,3,2], k = 1

› Output: 2

💡 Note: Day 1: bulb 1 is on. Day 2: bulb 3 is on, now we have bulbs 1 and 3 with exactly 1 bulb (position 2) between them that is off. Return day 2.

Example 2 — No Valid Pattern

$ Input: bulbs = [1,2,3], k = 1

› Output: -1

💡 Note: Day 1: bulb 1 on. Day 2: bulbs 1,2 on (no gap). Day 3: bulbs 1,2,3 on (no valid k=1 gap). Return -1.

Example 3 — Larger Gap

$ Input: bulbs = [1,5,3], k = 2

› Output: 3

💡 Note: Day 1: bulb 1 on. Day 2: bulbs 1,5 on (3 bulbs between). Day 3: bulb 3 on, now bulbs 1,3 have exactly k=2 bulbs between (positions 2,4). Return day 3.

Constraints

1 ≤ bulbs.length ≤ 2 × 10⁴
1 ≤ bulbs[i] ≤ bulbs.length
bulbs is a permutation of numbers from 1 to bulbs.length
0 ≤ k ≤ 2 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array of bulb positions and target gap k

Process

Turn on bulbs day by day, check for k-gaps

Output

First day when valid k-gap pattern exists

Key Takeaway

🎯 Key Insight: Only check newly lit bulbs against their immediate neighbors, as they form the smallest possible valid windows.

Asked in

G Google 25 f Facebook 18 a Amazon 12 M Microsoft 8

The key insight is that we only need to check newly lit bulbs against their immediate neighbors in sorted order. The optimal approach uses a sliding window technique to track adjacent lit bulbs, achieving O(n²) time in the worst case but much better in practice. For very large inputs, a Binary Indexed Tree can provide O(n log n) performance with efficient range queries.

Common Approaches

Approach	Time	Space	Notes
✓ Binary Indexed Tree (Fenwick Tree)	O(n log n)	O(n)	Use BIT to efficiently query ranges and find valid k-gaps
Sliding Window with Adjacent Tracking	O(n²)	O(n)	Track only adjacent lit bulbs to find valid windows efficiently
Brute Force Simulation	O(n³)	O(n)	Simulate each day and check all pairs of lit bulbs

Binary Indexed Tree (Fenwick Tree) — Algorithm Steps

Build BIT to track lit bulb positions
For each new bulb, query ranges of size k+2
Return first day when valid range is found

Visualization

Tap to expand

Step-by-Step Walkthrough

Update BIT

Mark new bulb position as lit

Range Query

Check if k+2 window has exactly 2 lit bulbs

Validate Gap

Confirm middle k positions are unlit

Code -

solution.c — C

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

typedef struct {
    int size;
    int* tree;
} BIT;

BIT* createBIT(int size) {
    BIT* bit = (BIT*)malloc(sizeof(BIT));
    bit->size = size;
    bit->tree = (int*)calloc(size + 1, sizeof(int));
    return bit;
}

void update(BIT* bit, int i, int val) {
    while (i <= bit->size) {
        bit->tree[i] += val;
        i += i & (-i);
    }
}

int query(BIT* bit, int i) {
    int res = 0;
    while (i > 0) {
        res += bit->tree[i];
        i -= i & (-i);
    }
    return res;
}

int rangeQuery(BIT* bit, int l, int r) {
    if (l > r) return 0;
    return query(bit, r) - query(bit, l - 1);
}

int solution(int* bulbs, int bulbsSize, int k) {
    BIT* bit = createBIT(bulbsSize);
    
    for (int day = 0; day < bulbsSize; day++) {
        int pos = bulbs[day];
        update(bit, pos, 1);
        
        // Check if there's a valid window ending at pos
        int left = pos - k - 1;
        if (left >= 1 && query(bit, left) > 0) {
            if (rangeQuery(bit, left + 1, pos - 1) == 0) {
                free(bit->tree);
                free(bit);
                return day + 1;
            }
        }
        
        // Check if there's a valid window starting at pos
        int right = pos + k + 1;
        if (right <= bulbsSize && query(bit, right) > 0) {
            if (rangeQuery(bit, pos + 1, right - 1) == 0) {
                free(bit->tree);
                free(bit);
                return day + 1;
            }
        }
    }
    
    free(bit->tree);
    free(bit);
    return -1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int bulbs[1000];
    int count = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            bulbs[count++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(bulbs, count, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Each BIT update and query takes O(log n), done n times

⚡ Linearithmic

Space Complexity

O(n)

BIT array stores cumulative counts for positions

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 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

Binary Indexed Tree (Fenwick Tree) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler