K Empty Slots

This page explains Java solution to problem K Empty Slots using TreeSet data structure.

Problem Statement

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: bulbs = [1,3,2], k = 1
Output: 2
Explanation:
On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0]
On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1]
On the third day: bulbs[2] = 2, second bulb is turned on: [1,1,1]
We return 2 because on the second day, there were two on bulbs with one off bulb between them.

Input: bulbs = [1,2,3], k = 1
Output: -1

Solution

package com.vc.hard;

import java.util.*;

class KEmptySlots {
    public int kEmptySlots(int[] bulbs, int k) {
        TreeSet<Integer> bulbSet = new TreeSet<>();
        for(int day = 0; day < bulbs.length; day++) {
            int bulbPosition = bulbs[day];
            Integer prevBulbPosition = bulbSet.lower(bulbPosition);
            Integer nextBulbPosition = bulbSet.higher(bulbPosition);
            if((prevBulbPosition != null && bulbPosition - prevBulbPosition - 1 == k) ||
                    (nextBulbPosition != null && nextBulbPosition - bulbPosition - 1 == k)) {
                return day + 1;
            }
            bulbSet.add(bulbPosition);
        }
        return -1;
    }
}

Time Complexity

O(N * log N) Where
N is total number of bulbs in an input array.

Space Complexity

O(N) Where
N is total number of bulbs in an input array.