Skip to main content

6207. Count Subarrays With Fixed Bounds

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

  • Contest 315

Python​

Brute Force (Timelimit Exceed)​

  • Time: O(N**2):
  • Space: O(1)
class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        if minK not in nums or maxK not in nums:
            return 0

        ans = 0
        for i in range(len(nums)):
            cmin, cmax = nums[i], nums[i]

            for j in range(i, len(nums)):
                cmax, cmin = max(cmax, nums[j]), min(cmin, nums[j])
                if cmax > maxK or cmin < minK:
                    break
                if cmin == minK and cmax == maxK:
                    ans += 1
                # print([i, j], (cmin, cmax), nums[i:j+1])
        return ans

Two Pointer​

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        n = len(nums)
        res, left = 0, 0
        pos1, pos2 = -1, -1
        for right in range(n):
            if nums[right] == minK:
                pos1 = right
            if nums[right] == maxK:
                pos2 = right
            if nums[right] < minK or nums[right] > maxK:
                left = right + 1
            res += max(0, min(pos1, pos2) - left + 1)

        return res