Leetcode # 3152. Special Array II

Problem

https://leetcode.com/problems/special-array-ii

Solution: Sliding Window

• 由於從 0 ~ (len(n) – 1) 的所有 indeses 都要建置
  所以使用 list 會比 dict 時間上效率更好
• 第 6 列的nums[1:] + [nums[-1]]是為了檢驗最後一個元素

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

class Solution:
  def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
    pre_parity = nums[0] % 2
    special_start = 0
    specials = [0] * len(nums) //{}
    for i, n in enumerate(nums[1:] + [nums[-1]], 1):
      cur_parity = n % 2
      if pre_parity != cur_parity: 
        pre_parity = cur_parity
        continue
      
      for s in range(special_start, i):
        specials[s] = i - 1
      special_start = i

    ans = [True] * len(queries)
    for i, q in enumerate(queries):
      if q[1] > specials[q[0]]:
        ans[i] = False

    return ans

Last Updated on 2024/12/09 by A1go