You have n bulbs in a row numbered from 1 to n. Initially, all the bulbs are turned off. On day i (for i from 0 to n-1), we turn on exactly one bulb. The position of this bulb is given by bulbs[i].

Given an integer k, return the minimum day number such that there exist two turned-on bulbs that have exactly k bulbs between them that are all turned off. If there isn’t such day, return -1.

Thinking Process

You have n bulbs in a row numbered from 1 to n. Initially, all the bulbs are turned off. On day i (for i from 0 to n-1), we turn on exactly one bulb. The position of this bulb is given by bulbs[i].

Given an integer k, return the minimum day number such that there exist two turned-on bulbs that have exactly k bulbs between them that are all turned off. If there isn’t such day, return -1.

  • Maintain a window [left, right] satisfying a constraint.
  • Expand right to grow; shrink left when invalid.
  • Fixed window: slide both pointers together.
Sliding window a b c d e window expand right, shrink left when invalid

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Fixed-size window (this problem) O(n) O(1) Window size known upfront
Variable-size window O(n) O(1) Expand/shrink until valid
Window + hash map O(n) O(k) Track character/count frequencies
Deque window max O(n) O(k) Monotonic deque for max/min in window

Examples

Example 1:

Input: bulbs = [1,3,2], k = 1
Output: 2
Explanation:
On day 1: bulbs[0] = 1, first bulb is turned on: [1, 0, 0]
On day 2: bulbs[1] = 3, third bulb is turned on: [1, 0, 1]
On day 3: bulbs[2] = 2, second bulb is turned on: [1, 1, 1]
We return 2 because on day 2, there were two on bulbs with one off bulb between them.

Example 2:

Input: bulbs = [1,2,3], k = 1
Output: -1
Explanation: No such day exists where two bulbs are on with exactly one bulb off between them.

Constraints

  • n == bulbs.length
  • 1 <= n <= 2 * 10^4
  • 1 <= bulbs[i] <= n
  • All values in bulbs are unique.
  • 0 <= k <= n

Algorithm Breakdown

Key Insight: Window Validation

The algorithm checks if a window [left, right] is valid by ensuring:

  • Both endpoints (left and right) are blooming bulbs
  • All bulbs between them (left+1 to right-1) are off (bloom later)

Validation Condition:

for(int i = left + 1; i < right; i++) {
    if(days[i] < days[left] || days[i] < days[right]) {
        // Invalid: bulb i blooms before one of the endpoints
    }
}

Why this works:

  • If days[i] < days[left]: bulb i blooms before left endpoint → cannot have k empty slots
  • If days[i] < days[right]: bulb i blooms before right endpoint → cannot have k empty slots
  • Only if all days[i] > max(days[left], days[right]): all middle bulbs bloom after both endpoints → valid window

Optimization: Early Termination

When an invalid bulb is found, we don’t need to check positions before it:

if(days[i] < days[left] || days[i] < days[right]) {
    left = i;  // Move left to invalid position
    right = i + k + 1;  // Update right accordingly
    break;  // Stop checking this window
}

This optimization ensures we don’t check redundant windows.

Complexity

Time Complexity: O(n)

  • Build days array: O(n) - single pass through bulbs
  • Sliding window: O(n) - each position visited at most once
    • When invalid bulb found, we skip to that position
    • Each position is checked at most once
  • Total: O(n)

Space Complexity: O(n)

  • Days array: O(n) - stores day for each position
  • Total: O(n)

Key Points

  1. Position-to-Day Mapping: Convert problem from “which position blooms on day i” to “which day does position i bloom”
  2. Window Size: Use window of size k + 2 (two endpoints + k empty slots)
  3. Validation Logic: All middle bulbs must bloom after both endpoints
  4. Early Termination: Skip invalid windows efficiently
  5. Result Calculation: Day when both endpoints are on = max(days[left], days[right])

Detailed Example Walkthrough

Example: bulbs = [6,5,8,9,7,1,10,2,3,4], k = 2

Step 1: Build days array
bulbs = [6, 5, 8, 9, 7, 1, 10, 2, 3, 4]
days  = [6, 8, 9, 10, 2, 3, 4, 5, 7, 1]
        (position 1 blooms on day 6, position 2 on day 8, etc.)

Step 2: Check window [0, 3] (positions 1 and 4, k=2 means positions 2,3 between)
Check positions 1, 2 (between 0 and 3):
- days[1] = 8, days[2] = 9
- days[0] = 6, days[3] = 10
- days[1] = 8 > days[0] = 6 ✓ and days[1] = 8 < days[3] = 10 ✗
- Invalid! Position 2 blooms before position 4

Step 3: Move to window [1, 4]
Check positions 2, 3 (between 1 and 4):
- days[2] = 9, days[3] = 10
- days[1] = 8, days[4] = 2
- days[2] = 9 > days[1] = 8 ✓ but days[2] = 9 > days[4] = 2 ✗
- Invalid! Position 3 blooms before position 5

Step 4: Move to window [4, 7]
Check positions 5, 6 (between 4 and 7):
- days[5] = 3, days[6] = 4
- days[4] = 2, days[7] = 5
- days[5] = 3 > days[4] = 2 ✓ but days[5] = 3 < days[7] = 5 ✗
- Invalid! Position 6 blooms before position 8

Step 5: Move to window [5, 8]
Check positions 6, 7 (between 5 and 8):
- days[6] = 4, days[7] = 5
- days[5] = 3, days[8] = 7
- days[6] = 4 > days[5] = 3 ✓ and days[6] = 4 < days[8] = 7 ✗
- Invalid! Position 7 blooms before position 9

Step 6: Move to window [6, 9]
Check positions 7, 8 (between 6 and 9):
- days[7] = 5, days[8] = 7
- days[6] = 4, days[9] = 1
- days[7] = 5 > days[6] = 4 ✓ but days[7] = 5 > days[9] = 1 ✗
- Invalid! Position 8 blooms before position 10

No valid window found → Return -1

Edge Cases

  1. k = 0: Two adjacent bulbs must both be on
  2. k = n-2: First and last bulbs with all middle bulbs off
  3. No solution: All bulbs bloom in order, no valid window
  4. Single valid window: Only one pair of positions satisfies condition

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Tags

Sliding Window, Two Pointers, Array, Medium

Key Takeaways

  • Maintain a window [left, right] satisfying a constraint.
  • Expand right to grow; shrink left when invalid.
  • Fixed window: slide both pointers together.

References

Template Reference