683. K Empty Slots

HardBinary Indexed TreeArrayOrdered SetSliding Window

Problem Description

In this problem, we have n light bulbs lined up in a row which are all initially turned off. The bulbs are numbered from 1 to n. There is a process where we turn on exactly one bulb per day in a sequence given by the array bulbs. This array represents the order in which bulbs are turned on. The goal is to find out on which day there will be two bulbs turned on with exactly k bulbs between them that are turned off.

For example, consider n = 5 bulbs and k = 1, with the order of bulbs being turned on as [3, 1, 5, 4, 2]. After day 3, bulbs at positions [1, 3, 4] are on with one bulb between 1 and 3 being off, but it doesn't fulfill the requirement as we need k = 1 bulb turned off between two bulbs that are turned on. It's on the 5th day when bulb 2 is turned on that we have bulbs 1 and 3 on with exactly one bulb between them off.

If there is no such situation where two turned-on bulbs have exactly k bulbs between them that are all turned off, we return -1.

Intuition

The key to solving this problem is efficiently keeping track of the number of turned-off bulbs between any two turned-on bulbs, and be able to quickly update and query this information as we turn on additional bulbs. A naive approach would be to check all gaps between bulbs every time we turn on a new bulb, but this would be extremely inefficient as it would take O(n^2) time in the worst case.

Instead, we can use a Binary Indexed Tree (BIT), also known as Fenwick Tree, as an efficient data structure to maintain the prefix sums of the state of the bulbs (on or off). Specifically, we can track the running total of bulbs turned on, thereby allowing us to query the number of bulbs turned on up to any given position with tree.query(pos).

Each time we turn on a bulb at position x, we update the BIT at x to indicate that the bulb is now on. Immediately after turning on a bulb, we want to check if there is a bulb that is turned on either k + 1 positions to the left or right of the current bulb. If such a bulb exists, we also need to make sure all the bulbs between these two positions are off. This can be quickly checked using the BIT by verifying that the number of bulbs turned on in the range between them is zero (excluding the end bulbs).

If the conditions are met, then we have found the day when the requirements are fulfilled, and we return the index of the current day. If no such day exists by the end of the process, we return -1.

Using a BIT gives us an efficient solution with O(n log n) time complexity because each update and query operation on the BIT requires O(log n) time, and we perform at most n such operations—one for each day.

Learn more about Sliding Window patterns.

Solution Approach

The solution uses a Binary Indexed Tree (BIT) or Fenwick Tree to efficiently compute prefix sums of the bulbs' states. The idea behind the BIT is to allow fast updates and queries for cumulative frequencies (or sums) in O(log n) time which is much more efficient than using a simple array approach for the same purpose.

Here is a step-by-step walk-through of the implementation:

Initializing the Binary Indexed Tree (BIT): The BIT is initialized with a size of n + 1, which corresponds to the number of bulbs plus one. This additional space is to allow the BIT to use 1-based indexing which aligns with how we reference bulbs. The BIT class contains two operations: update and query.
- update(x, delta): This function adds delta to position x in the BIT and updates all subsequent necessary positions. We only call this function with delta = 1, as we turn on a bulb.
- query(x): This function returns the cumulative sum of the turned-on bulbs up to position x, which is useful to check how many bulbs are turned on up to a certain point.
Processing Bulbs in Given Order: The bulbs array represents the order in which bulbs are turned on. We iterate over this array, and for each bulb that gets turned on, we perform the BIT update at the given position.
Checking Bulbs to Left and Right for Conditions: After each bulb x is turned on, we check whether there is a previously turned-on bulb at positions x - k - 1 (to the left) and x + k + 1 (to the right) such that exactly k bulbs between them are all turned off.
- We use the query function to get the number of bulbs turned on in the range (y, x-1) for the left check and (x, y-1) for the right check. If either route returns a count of 0, it indicates that all the bulbs between the two checked positions are off, and thus we found a valid scenario.
Returning the Result: If the condition is met at any point during the iteration, we return the 1-based index of the day (i.e., i) on which the condition was satisfied. If no such day is found by the time we finish processing all bulbs, the function returns -1.

The BIT is instrumental in this solution since it keeps the time complexity manageable. A direct approach using a regular array to check the state of bulbs between two positions would not be feasible because it would require O(n^2) time in the worst case. With the BIT, we maintain an optimal O(n log n) efficiency due to the logarithmic time complexity of updates and queries.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the Binary Indexed Tree (BIT). Consider we have n = 4 bulbs and k = 1, with the order of bulbs being turned on as [2, 1, 4, 3]. The bulbs are initially all off, denoted by 0: [0, 0, 0, 0].

Initialize the BIT with a size of n + 1 for 1-based indexing.
Turn on bulb 2 on the first day: [0, 1, 0, 0]. Update the BIT at position 2.
- After turning on the bulb, check positions 2 - k - 1 = 0 and 2 + k + 1 = 4. No bulbs are on at those positions, so no valid scenario is found.
Turn on bulb 1 on the second day: [1, 1, 0, 0]. Update the BIT at position 1.
- After turning on the bulb, check positions 1 - k - 1 = -1 (invalid position) and 1 + k + 1 = 3. No bulb is on at position 3, so no valid scenario is found.
Turn on bulb 4 on the third day: [1, 1, 0, 1]. Update the BIT at position 4.
- After turning on the bulb, check positions 4 - k - 1 = 2 and 4 + k + 1 = 6 (invalid position). A bulb is on at position 2, but since the BIT query for range (2, 3) returns 1 (indicating that there's one bulb on in this range), it does not fit the condition k = 1 (we need 0).
Turn on bulb 3 on the fourth day: [1, 1, 1, 1]. Update the BIT at position 3.
- After turning on the bulb, check positions 3 - k - 1 = 1 and 3 + k + 1 = 5 (invalid position). A bulb is on at position 1, and BIT query for range (1, 2) returns 0, meeting our condition: no bulbs are on between positions 1 and 3, fulfilling the requirement that there's exactly one bulb (k = 1) that's off between them.

Since we have found a valid scenario on the fourth day when bulb 3 was turned on, we return the day number, which is 4. If we had not found a valid scenario after turning on all the bulbs, we would have returned -1.

Using the BIT, we could efficiently check the conditions after each bulb was turned on, leading to a timely discovery of the solution.

Solution Implementation

1from typing import List
2
3class BinaryIndexedTree:
4    def __init__(self, size):
5        self.size = size
6        # Initialize the Binary Indexed Tree with 0s
7        self.tree_array = [0] * (size + 1)
8
9    def update(self, index, delta):
10        # Update the tree by adding 'delta' to the value at 'index'
11        while index <= self.size:
12            self.tree_array[index] += delta
13            index += index & -index
14
15    def query(self, index):
16        # Calculate the prefix sum up to 'index'
17        sum = 0
18        while index:
19            sum += self.tree_array[index]
20            index -= index & -index
21        return sum
22
23class Solution:
24    def kEmptySlots(self, bulbs: List[int], k: int) -> int:
25        # Number of bulbs
26        n = len(bulbs)
27        # Initialize a tree to represent bulb status, 0 for off, 1 for on
28        tree = BinaryIndexedTree(n)
29        # Visibility list to keep track of switched-on bulbs
30        visibility = [False] * (n + 1)
31        # Loop through each bulb switch event
32        for day, bulb in enumerate(bulbs, 1):
33            # Turn on the bulb and update the tree
34            tree.update(bulb, 1)
35            # Set the bulb as turned on
36            visibility[bulb] = True
37            # Check for bulbs 'k' steps away before the current one
38            left_bulb_position = bulb - k - 1
39            # If the position of the left bulb is valid and the bulb is on
40            if left_bulb_position > 0 and visibility[left_bulb_position]:
41                # Ensure there are 'k' empty slots between them
42                if tree.query(bulb - 1) - tree.query(left_bulb_position) == 0:
43                    # Day number when the condition is met
44                    return day
45            # Check for bulbs 'k' steps away after the current one
46            right_bulb_position = bulb + k + 1
47            # If the position of the right bulb is valid and the bulb is on
48            if right_bulb_position <= n and visibility[right_bulb_position]:
49                # Ensure there are 'k' empty slots between them
50                if tree.query(right_bulb_position - 1) - tree.query(bulb) == 0:
51                    # Day number when the condition is met
52                    return day
53        # If no such day is found, return -1
54        return -1
55
56# Example usage:
57# solution = Solution()
58# print(solution.kEmptySlots([1, 3, 2], 1)) # Expected output: 2
59

1class Solution {
2    public int kEmptySlots(int[] bulbs, int k) {
3        // Total number of bulbs
4        int totalBulbs = bulbs.length;
5
6        // Create a Binary Indexed Tree with totalBulbs number of elements
7        BinaryIndexedTree tree = new BinaryIndexedTree(totalBulbs);
8
9        // This vis array keeps track of which bulbs are turned on
10        boolean[] isLit = new boolean[totalBulbs + 1];
11
12        // Iterate over each bulb that is turned on per day
13        for (int day = 1; day <= totalBulbs; ++day) {
14            // Get the bulb to be turned on for this day
15            int currentBulb = bulbs[day - 1];
16
17            // Update the Binary Indexed Tree to indicate this bulb is on
18            tree.update(currentBulb, 1);
19
20            // Mark the current bulb as lit in the isLit array
21            isLit[currentBulb] = true;
22
23            // Check the previous bulb that is at a distance of k slots away
24            int previousBulb = currentBulb - k - 1;
25
26            // If the previous bulb is within range and is on, and there are no bulbs lit between them
27            if (previousBulb > 0 && isLit[previousBulb] && tree.query(currentBulb - 1) - tree.query(previousBulb) == 0) {
28                // Return the current day as it satisfies the condition
29                return day;
30            }
31
32            // Check the next bulb that is at a distance of k slots away
33            int nextBulb = currentBulb + k + 1;
34
35            // If the next bulb is within range and is on, and there are no bulbs lit between them
36            if (nextBulb <= totalBulbs && isLit[nextBulb] && tree.query(nextBulb - 1) - tree.query(currentBulb) == 0) {
37                // Return the current day as it satisfies the condition
38                return day;
39            }
40        }
41
42        // If no valid day is found where k slots are empty between two bulbs, return -1
43        return -1;
44    }
45}
46
47class BinaryIndexedTree {
48    // Total number of elements in the tree
49    private int size;
50  
51    // The tree array used for a Binary Indexed Tree data structure
52    private int[] treeArray;
53
54    public BinaryIndexedTree(int size) {
55        this.size = size;
56        this.treeArray = new int[size + 1];
57    }
58
59    // Updates the Binary Indexed Tree with the value of delta at position x
60    public void update(int x, int delta) {
61        for (; x <= size; x += x & -x) {
62            treeArray[x] += delta;
63        }
64    }
65
66    // Queries the Binary Indexed Tree to get the cumulative frequency up to position x
67    public int query(int x) {
68        int sum = 0;
69        for (; x > 0; x -= x & -x) {
70            sum += treeArray[x];
71        }
72        return sum;
73    }
74}
75

1#include <vector>
2#include <cstring> // For memset
3
4using namespace std;
5
6// Binary Indexed Tree (BIT) or Fenwick Tree helps to efficiently calculate prefix sums in a table of numbers.
7class BinaryIndexedTree {
8public:
9    int size; // Size of the array
10    vector<int> tree; // BIT data structure
11
12    // Constructor to initialize the BIT with a given size.
13    BinaryIndexedTree(int n): size(n), tree(n + 1) {}
14
15    // Updates the BIT at a specific index by a value delta.
16    void update(int index, int delta) {
17        for (; index <= size; index += index & -index) {
18            tree[index] += delta;
19        }
20    }
21
22    // Queries the prefix sum from the start to a specific index.
23    int query(int index) {
24        int sum = 0;
25        for (; index; index -= index & -index) {
26            sum += tree[index];
27        }
28        return sum;
29    }
30};
31
32class Solution {
33public:
34    // Method to find the first day where there are 'k' empty slots between two bulbs.
35    int kEmptySlots(vector<int>& bulbs, int k) {
36        int n = bulbs.size();
37        BinaryIndexedTree bit(n); // Instance of BIT
38        vector<bool> isOn(n + 1, false); // Tracks if a bulb is turned on
39
40        for (int day = 1; day <= n; ++day) {
41            int current = bulbs[day - 1];
42            bit.update(current, 1); // Turn on the bulb at position 'current' and update BIT
43            isOn[current] = true;
44
45            // Check the left side of the current bulb
46            int leftNeighbor = current - k - 1;
47            if (leftNeighbor > 0 && isOn[leftNeighbor] && bit.query(current - 1) - bit.query(leftNeighbor) == 0) {
48                return day;
49            }
50
51            // Check the right side of the current bulb
52            int rightNeighbor = current + k + 1;
53            if (rightNeighbor <= n && isOn[rightNeighbor] && bit.query(rightNeighbor - 1) - bit.query(current) == 0) {
54                return day;
55            }
56        }
57
58        return -1; // Return -1 if no such day is found
59    }
60};
61

1// The size of our indexed data structure
2let size: number = 0;
3// The actual storage for our binary indexed tree
4let treeArray: number[];
5
6/**
7 * Initialize the tree with the given number of elements.
8 * @param {number} n - The number of elements
9 */
10function initializeTree(n: number): void {
11    size = n;
12    treeArray = Array(n + 1).fill(0);
13}
14
15/**
16 * Updates the tree with a value delta at the given index x.
17 * @param {number} x - The index at which to update
18 * @param {number} delta - The value to add
19 */
20function updateTree(x: number, delta: number): void {
21    for (; x <= size; x += x & -x) {
22        treeArray[x] += delta;
23    }
24}
25
26/**
27 * Queries the sum of the range up to index x.
28 * @param {number} x - The index up to which to query
29 * @returns {number} - The sum of the range up to x
30 */
31function queryTree(x: number): number {
32    let sum = 0;
33    for (; x > 0; x -= x & -x) {
34        sum += treeArray[x];
35    }
36    return sum;
37}
38
39/**
40 * Finds the day on which the two bulbs turned on have exactly k bulbs off between them.
41 * @param {number[]} bulbs - The sequence of bulbs being turned on
42 * @param {number} k - The number of bulbs that should be off between two on bulbs
43 * @returns {number} - The day number when the condition is met or -1 if it never happens
44 */
45function kEmptySlots(bulbs: number[], k: number): number {
46    const n = bulbs.length;
47    initializeTree(n);
48    const visited: boolean[] = Array(n + 1).fill(false);
49
50    for (let i = 1; i <= n; ++i) {
51        const currentBulb = bulbs[i - 1];
52        updateTree(currentBulb, 1);
53        visited[currentBulb] = true;
54
55        const leftNeighbor = currentBulb - k - 1;
56        if (leftNeighbor > 0 && visited[leftNeighbor] && queryTree(currentBulb - 1) - queryTree(leftNeighbor) === 0) {
57            return i;
58        }
59
60        const rightNeighbor = currentBulb + k + 1;
61        if (rightNeighbor <= n && visited[rightNeighbor] && queryTree(rightNeighbor - 1) - queryTree(currentBulb) === 0) {
62            return i;
63        }
64    }
65    return -1;
66}
67

Time and Space Complexity

Time Complexity

The time complexity of the kEmptySlots function is primarily governed by the update and query functions of the BinaryIndexedTree class. These two functions are called for each bulb being turned on, which happens n times (n is the number of bulbs).

Each call to update and query functions has a time complexity of O(log n) as it involves traversing the tree structure in the worst case up to a depth proportional to the logarithm of the number of elements n.
Since both update and query functions are called once for each of the n bulbs, the overall time complexity of the provided algorithm is O(n log n).

Space Complexity

The space complexity of the kEmptySlots function is determined by the space needed to store:

The Binary Indexed Tree (tree.c), which requires O(n) space since it is a list with n+1 elements (n being the number of bulbs).
The vis list, which also requires O(n) space, as it is a list with n+1 elements used to keep track of which bulbs have been turned on.

Thus, the total space complexity is O(n), accounting for the storage required for both tree.c and vis.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which two pointer techniques do you use to check if a string is a palindrome?

Fast-slow pointers

Two pointers moving in opposite direction

Sliding window

Prefix sum

I don’t know