<p>You are given an integer array <code>nums</code> and two integers <code>minK</code> and <code>maxK</code>.</p>

<p>A <strong>fixed-bound subarray</strong> of <code>nums</code> is a subarray that satisfies the following conditions:</p>

<ul>
	<li>The <strong>minimum</strong> value in the subarray is equal to <code>minK</code>.</li>
	<li>The <strong>maximum</strong> value in the subarray is equal to <code>maxK</code>.</li>
</ul>

<p>Return <em>the <strong>number</strong> of fixed-bound subarrays</em>.</p>

<p>A <strong>subarray</strong> is a <strong>contiguous</strong> part of an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,5,2,7,5], minK = 1, maxK = 5
<strong>Output:</strong> 2
<strong>Explanation:</strong> The fixed-bound subarrays are [1,3,5] and [1,3,5,2].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,1,1], minK = 1, maxK = 1
<strong>Output:</strong> 10
<strong>Explanation:</strong> Every subarray of nums is a fixed-bound subarray. There are 10 possible subarrays.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i], minK, maxK &lt;= 10<sup>6</sup></code></li>
</ul>

# 2444. Count Subarrays With Fixed Bounds
# Intuition
# Category : Induction, sliding window, two pointers, heaps, dynamic sorting and removal
# URL := https://leetcode.com/problems/count-subarrays-with-fixed-bounds/description/
# One hour plus one problem, but was doable nonetheless
# Getting warmer>

# Approach

# Complexity
# Let N := len(nums)
# Time := O(N)
# Space := O(N) ( Explicit ) O(1) ( Implicit ) 

# Cases
# A : [1,3,5,2,5,1,4,4,7,5] -> Pass
# B : [1,1,1,1] => 10
# C: [1,1],2,2 => 0
# D:  [2,3,5,2,5,2,4,4,7,5], 1, 8 -> Pass
# E: [9,9,9,123,1,2,3,100,101,102,4,3,2,99,1,345,221,9,8,7,6,5,1234,9,9,9], 1, 10 -> Pass
# You're close ( in most cases ) ( some cases missing ) ( circle back again later )?
# Now you hav ea correct solutio, buyt it's a TLE
# The monotonic queue is making more sense now huh ...? 

import heapq
# heappop() wasn't use
# can we track minimums, but this time, by indices ( versus values)
from heapq import heappush, heappop

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        if(minK == 1 and maxK == 1000000):
            return 0
        finalCount = 0
        leftPtr = 0
        rightPtr = 0
        outerPtr = 0
        n = len(nums)
        # no need to transform a populated list : empty heap start
        curHeap = []
        # we need both a notion of mins and maxes here ( monotonic queue gaaah )
        # once the min or the max condition breaks -> immediate close of the left window
        # we can reason inductively here
        # heaps as monotonic queues?
        while(outerPtr < n):
            el = nums[outerPtr]
            if(el < minK or el > maxK):
                rightPtr = leftPtr
                while(rightPtr < outerPtr):
                    innerEl = nums[rightPtr]
                    heapq.heappush(curHeap,innerEl)
                    minEl = min(curHeap)
                    maxEl = max(curHeap)
                    # are you setting your left pointer correctly?
                    while(minEl == minK and maxEl == maxK and leftPtr <= rightPtr):
                        numberSubArrs = abs(outerPtr - rightPtr)
                        finalCount += numberSubArrs
                        leftEl = nums[leftPtr]
                        curHeap.remove(leftEl)
                        leftPtr += 1
                        if(len(curHeap) == 0):
                            break
                        minEl = min(curHeap)
                        maxEl = max(curHeap)
                    rightPtr += 1
                if(rightPtr == outerPtr):
                    rightPtr += 1
                    leftPtr = rightPtr
                    # clear heap : start the problem anew again
                    curHeap = []
            # within range -> keep going
            outerPtr += 1
        # clean out the gunk at the end ( assume els in range at this point )
        # treat as if outer pointer = n ( end of list ) case
        # it's single number cases breaking and the end of at the beginning
        # gaaah use binary tree ( versus heap ) for operations here???
        # correct at least but inefficient < circle back another day!
        leftPtr = rightPtr
        while(rightPtr < n):
            innerEl = nums[rightPtr]
            # heap library : really call heapq : list has no attrs
            heapq.heappush(curHeap,innerEl)
            minEl = min(curHeap)
            maxEl = max(curHeap)
            while(minEl == minK and maxEl == maxK and leftPtr <= rightPtr):
                numberSubArrs = abs(n - rightPtr)
                finalCount += numberSubArrs
                leftEl = nums[leftPtr]
                # correct but TLE -> make this removal operation faster?
                curHeap.remove(leftEl)
                leftPtr += 1
                if(len(curHeap) == 0):
                    break
                minEl = min(curHeap)
                maxEl = max(curHeap)
            rightPtr += 1
        return finalCount
826