683. K Empty Slots
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
andquery
.-
update(x, delta): This function adds
delta
to positionx
in the BIT and updates all subsequent necessary positions. We only call this function withdelta = 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 positionsx - k - 1
(to the left) andx + k + 1
(to the right) such that exactlyk
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 of0
, it indicates that all the bulbs between the two checked positions are off, and thus we found a valid scenario.
- We use the
-
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 EvaluatorExample 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
and2 + k + 1 = 4
. No bulbs are on at those positions, so no valid scenario is found.
- After turning on the bulb, check positions
-
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) and1 + k + 1 = 3
. No bulb is on at position 3, so no valid scenario is found.
- After turning on the bulb, check positions
-
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
and4 + 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).
- After turning on the bulb, check positions
-
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
and3 + 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.
- After turning on the bulb, check positions
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
andquery
functions has a time complexity ofO(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 elementsn
. -
Since both
update
andquery
functions are called once for each of then
bulbs, the overall time complexity of the provided algorithm isO(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 requiresO(n)
space since it is a list withn+1
elements (n
being the number of bulbs). -
The
vis
list, which also requiresO(n)
space, as it is a list withn+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.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!