Leetcode # 2444. Count Subarrays With Fixed Bounds

Problem

https://leetcode.com/problems/count-subarrays-with-fixed-bounds

fixed_bound_subarray :=

1. nums[i:j]; 0 <= i, j < len(nums); i <= j
2. min(fixed_bound_subarray) == minK
   ≡ (∀ num ∈ fixed_bound_subarray, num <= minK)
   (∃ min_num ∈ fixed_bound_subarray, min_num == minK)
3. max(fixed_bound_subarray) == maxK

Solution

nums[left] … (minK/maxK … maxK/minK) … nums[right]

• minK <= nums[i] <= maxK, for i in [left, right]
• (minK/maxK … maxK/minK): minK/maxK pair (if last_max != -1 and last_min != -1:)
  There’s no other minK/maxK pair in (minK/maxK … maxK/minK)
• nums[left] … minK/maxK: min(last_min, last_max) - left + 1
• maxK/minK … nums[right]: for right in range(len(nums)):

ex: minK = 0, maxK = 2

1101 ⇒ ×
11012 ⇒ 11012, 1012, 012 (3)
110121 ⇒ 110121, 10121, 0121 (3)
1101211 ⇒ 1101211, 101211, 01211 (3)
11012111 ⇒ 11012111, 1012111, 012111 (3)
110121110 ⇒ 110121110, 10121110, 0121110, 121110, 21110 (5)
1101211100 ⇒ 1101211100, 101211100, 01211100, 1211100, 211100 (5)
11012111003 ⇒ ×

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

class Solution:
  def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
    ans = left = 0
    last_max = last_min = -1
    for right in range(len(nums)):
      if nums[right] > maxK or nums[right] < minK:
        left = right + 1
        last_max = last_min = -1
      else:
        if nums[right] == maxK:
          last_max = right
        if nums[right] == minK:
          last_min = right
        
      # update ans
      if last_max != -1 and last_min != -1:
        ans += min(last_min, last_max) - left + 1
    
    return ans      

Last Updated on 2023/09/06 by A1go