How hard is LeetCode 683. K Empty Slots?

LeetCode 683. K Empty Slots is rated Hard on LeetCode.

What is the time complexity of LeetCode 683. K Empty Slots?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 683. K Empty Slots?

The Python solution on this page uses O(n), where n is the number of bulbs auxiliary space.

Is LeetCode 683. K Empty Slots a premium problem?

Yes. LeetCode 683. K Empty Slots is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

K Empty Slots — LeetCode 683 Python Solution

HardLeetCode PremiumBinary Indexed TreeSegment TreeQueueArrayOrdered SetSliding WindowMonotonic QueueHeap (Priority Queue)

Problem: #683
Pattern: Sliding Window
Reading time: 6 min
Source: leetcode.com

The problem

You have n bulbs in a row numbered from 1 to n. Initially, all the bulbs are turned off.

Example

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]

Python solution

Python

class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x, delta):
        while x <= self.n:
            self.c[x] += delta
            x += x & -x

    def query(self, x):
        s = 0
        while x:
            s += self.c[x]
            x -= x & -x
        return s


class Solution:
    def kEmptySlots(self, bulbs: List[int], k: int) -> int:
        n = len(bulbs)
        tree = BinaryIndexedTree(n)
        vis = [False] * (n + 1)
        for i, x in enumerate(bulbs, 1):
            tree.update(x, 1)
            vis[x] = True
            y = x - k - 1
            if y > 0 and vis[y] and tree.query(x - 1) - tree.query(y) == 0:
                return i
            y = x + k + 1
            if y <= n and vis[y] and tree.query(y - 1) - tree.query(x) == 0:
                return i
        return -1

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n), where n is the number of bulbs auxiliary

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 683. K Empty Slots is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Sliding Window.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 683. K Empty Slots?: LeetCode 683. K Empty Slots is rated Hard on LeetCode.
What is the time complexity of LeetCode 683. K Empty Slots?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 683. K Empty Slots?: The Python solution on this page uses O(n), where n is the number of bulbs auxiliary space.
What topics does LeetCode 683. K Empty Slots cover?: LeetCode 683. K Empty Slots is tagged Binary Indexed Tree, Segment Tree, Queue, Array, Ordered Set, Sliding Window, Monotonic Queue and Heap (Priority Queue) on LeetCode.
Is LeetCode 683. K Empty Slots a premium problem?: Yes. LeetCode 683. K Empty Slots is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.