We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

K Empty Slots

Number: 683

Difficulty: Hard

Paid? Yes

Companies: Google

Problem Description

Given n bulbs in a row (numbered 1 to n) that start off, one bulb is turned on per day following the order given in the array bulbs (where bulbs[i] = x indicates that on day i+1 the bulb at position x is turned on). The goal is to determine the minimum day such that there exists a pair of turned on bulbs with exactly k bulbs (all still off) between them. If no such day exists, return -1.

Key Insights

  • Preprocess the bulbs array into a days array where days[i] indicates the day the bulb at position i+1 is switched on.
  • Use a sliding window of size k+2: the window’s left and right boundaries represent the two bulbs and the interval between should all turn on later.
  • For each window, check that every bulb between the boundaries turns on later than both the left and right bulbs.
  • Return the minimum maximum day for any valid window; if none exist, return -1.

Space and Time Complexity

Time Complexity: O(n * k) in the worst-case using the sliding window approach. More advanced data structures (e.g., segment trees or binary indexed trees) can achieve O(n log n). Space Complexity: O(n) for the additional days array.

Solution

The solution uses a transformation step to create a days array mapping bulb positions to the day they are turned on. Then, a sliding window of length k+2 is moved along the days array. For each window, we ensure that every bulb strictly between the two boundaries turns on later than both boundaries. If the condition holds, the answer is updated with the maximum of the turning on days at the boundaries (as that is the day when both boundary bulbs are already on). If the condition fails, reposition the window starting from the bulb that violated the rule.

Code Solutions

def kEmptySlots(bulbs, k):
    n = len(bulbs)
    # days[i] stores when the bulb at position i+1 is turned on.
    days = [0] * n
    for day, bulb in enumerate(bulbs):
        days[bulb - 1] = day + 1

    ans = float('inf')
    left, right = 0, k + 1

    # Slide the window through the days array.
    while right < n:
        valid = True
        for i in range(left + 1, right):
            if days[i] < days[left] or days[i] < days[right]:
                valid = False
                left = i
                right = left + k + 1
                break
        if valid:
            current_day = max(days[left], days[right])
            ans = min(ans, current_day)
            left = right
            right = left + k + 1

    return -1 if ans == float('inf') else ans

# Example Usage:
print(kEmptySlots([1, 3, 2], 1))
← Back to All Questions