Leetcode # 683. K Empty Slots

Problem

https://leetcode.com/problems/k-empty-slots

What I Tried
[Time Limit Exceeded  27 / 61 testcases passed]

Time Complexity: O(len(bulbs) ** 2)
Space Complexity: O(len(bulbs))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def kEmptySlots(self, bulbs: List[int], k: int) -> int:
    segments = [[1, len(bulbs)]]
    for i, x in enumerate(bulbs):
      for j, segment in enumerate(segments):
        if x >= (start := segment[0]) \
            and x <= (end := segment[1]):
          new_segments = [[a, b] \
            for a, b in [[start, x - 1], [x + 1, end]] \
            if a <= b
          ]
          for a, b in new_segments:
            if b - a + 1 == k:
              if a == 1 or b == len(bulbs): continue
              return i + 1
          segments = segments[:j] + new_segments + segments[j + 1:]
    return -1

Time Complexity: O(len(bulbs) ** 2)
Space Complexity: O(len(bulbs))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def kEmptySlots(self, bulbs: List[int], k: int) -> int:
    turned_on = set()
    for i, x in enumerate(bulbs):
      first_exists = (first := x - k - 1) in turned_on
      final_exists = (final := x + k + 1) in turned_on
      if first_exists or final_exists:
        blocks = [
          y for y in turned_on \
          if (first_exists and y > first and y < x) \
          or (final_exists and y > x and y < final)
        ]
        if not blocks:
          return i + 1
        
      turned_on.add(x)

    return -1

Solution: Sliding Window

days[i] := the day i_th bulb was turned on

• sliding windows: (left, right := left + (k + 1))
• find min([max(days[i], days[i + (k + 1)])
  　for i in range(1, len(days) – k)
  　if all([days[j] > days[i] and days[j] > days[i + (k + 1)] for j in range(i + 1, i + (k + 1))])
  ])

⭐ 用 for … + if … else … 達成 all(… for …)

for ...:
  if not condition:
    ....
    break
else: ...

≡ all(condition for ...)

⚠️ 注意！

if和else的縮排不同
只有在for裡所有if都沒有被觸發，才會在最後一次的if執行else

Code

Time Complexity: O(len(bulbs))
Space Complexity: O(len(bulbs))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def kEmptySlots(self, bulbs: List[int], k: int) -> int:
    days = [0] * len(bulbs)
    for i, x in enumerate(bulbs, 1):
      days[x - 1] = i

    ans = float('inf')
    left, right = 0, k + 1
    print(days)
    while right < len(days):
      max_day = max(days[left], days[right])
      for i in range(left + 1, right):
        if days[i] < max_day:
          left = i
          break
      else:
        ans = min(ans, max_day)
        left = right
      right = left + k + 1

    return ans if ans < float('inf') else -1

Last Updated on 2025/06/24 by A1go