K Empty Slots

Problem Statement

In this problem, you are provided with a sequential process of turning on bulbs in a linear arrangement where each bulb is initially off. Each bulb can be uniquely identified by its position, ranging from 1 to n. The sequence of turning the bulbs on is dictated by the array bulbs, where bulbs[i] = x indicates that on the (i+1)th day, the bulb at position x will be turned on.

The challenge is to determine the minimum day number on which there exists a scenario where two bulbs are turned on with exactly k bulbs between them that are all off. If no such scenario arises until all bulbs are turned on, the answer should be -1.

Examples

Example 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.

Example 2

Input:

bulbs = [1,2,3], k = 1

Output:

-1

Constraints

• n == bulbs.length
• 1 <= n <= 2 * 104
• 1 <= bulbs[i] <= n
• bulbs is a permutation of numbers from 1 to n.
• 0 <= k <= 2 * 104

Approach and Intuition

To solve this problem, you need to keep track of which bulbs are turned on during each passing day and check the specified condition about the bulbs in between them. Use the below steps based on the provided examples and constraints:

1. Begin by initializing an empty structure to store the state of each bulb (either on or off).
2. Simulate each day's action by turning on the bulb as specified in the bulbs array.
3. After turning on a bulb each day, check for pairs of bulbs that are already on to see if they satisfy the condition of having exactly k bulbs between them that are all off.
4. If on any given day this condition is satisfied, capture and return that day as the result.
5. If all bulbs are turned on and no such pair is found that satisfies the conditions, return -1.

Example Analysis

• Example 1:

  • Sequence of operations:
    • Day 1: Turn on bulb at position 1 -> [1,0,0]
    • Day 2: Turn on bulb at position 3 -> [1,0,1]
    • Day 3: Turn on bulb at position 2 -> [1,1,1]
  • At Day 2, bulbs at positions 1 and 3 are on with exactly one bulb (position 2) off in between them, satisfying the condition k=1.

• Example 2:

  • All bulbs are turned on in sequence with no bulbs off between any two turned on bulbs, thus the output is -1.

This approach leverages the sequencing details provided by the bulbs array and condition checks implemented in a straightforward manner as the bulbs are turned on day-by-day.

Solutions

class Solution {
    public int checkSlots(int[] plants, int gap) {
        int[] bloomDays = new int[plants.length];
        for (int index = 0; index < plants.length; index++) {
            bloomDays[plants[index] - 1] = index + 1;
        }

        int minimumDays = Integer.MAX_VALUE;
        int start = 0, end = gap + 1;

        loop: while (end < bloomDays.length) {
            for (int i = start + 1; i < end; i++) {
                if (bloomDays[i] < bloomDays[start] || bloomDays[i] < bloomDays[end]) {
                    start = i;
                    end = i + gap + 1;
                    continue loop;
                }
            }
            minimumDays = Math.min(minimumDays, Math.max(bloomDays[start], bloomDays[end]));
            start = end;
            end = start + gap + 1;
        }

        return minimumDays < Integer.MAX_VALUE ? minimumDays : -1;
    }
}