Python - 2 Sliding Window Solutions
\n# APPROACH 1- NOT O(1) SPACE\n\nThere are some things to take care of in this problem. We cannot simply consider one window to be valid and just increment cou
\n# **APPROACH 1- NOT O(1) SPACE**\n\nThere are some things to take care of in this problem. We cannot simply consider one window to be valid and just increment count by 1.\n\nConsider this ->\n\n\t\tnums = [2,2,2,1,2,2,1,2,2,2] and k = 2\n\t\t\t\t0 1 2 3 4 5 6 7 8 9\n\t\t\nSo, if we use the sliding window approach, then we will start from index 0 and until the count of odd numbers does not become k, we will keep increasing window size. Now just by looking at the array you will see that when index is  6 then it will have two odd numbers from 0th index to 6th index.\n\nSo we will have a valid window with k odd numbers -\n\n\t\t\t[2,2,2,1,2,2,1]\n\nBut, at this moment, we cannot simply do count += 1. Just think about it. If [2,2,2,1,2,2,1] is a valid subarray with k odd numbers, then how many subarrays of this are also valid?\n\n\tThese are all valid subarrays with k odd numbers\n\t[2,2,2,1,2,2,1]\n\t[2,2,1,2,2,1]\n\t[2,1,2,2,1]\n\t[1,2,2,1]\n\t\nThis means, we cannot do count += 1 only. We have to check for a particular nice subarray, how many total nice subarrays are possible.\n\nAnd to find that, just see above what is the smallest possible subarray. It is [1,2,2,1]. Why we were not able to get more subarrays smaller than it? Because we would\'ve lost one odd number and that would\'ve violated the condition of k odd numbers.\n\nSo this means, just see how many numbers are there between the beginning of the window and the first odd number in the window i.e., the leftmost odd number.\n\nFinally, we will get a general formula as \n\t\n\t\t(index of leftmost odd number in current window - index of beginning of window) + 1\n\t\t\nSo basically, we want to keep track of not just the odd numbers but also their indices. \n\nAnd so I used a queue here to keep all the indices in it from left to right as we encounter odd numbers so that to calculate the count, we can simply get the first item in the queue as that will always be the leftmost odd number index of current window.\n\nAnd as we shrink the window, we will keep checking if the item we are removing from window is an odd number or not. If yes, that means we need to remove the leftmost item from queue as well. \n\n\n```\ndef numberOfSubarrays(self, nums: List[int], k: int) -> int:\n        subarrayCount = 0\n        \n        i,j = 0,0\n\n        queue = deque()\n        \n\n        while( j < len(nums) ):\n            # If we encounter an odd number push the index of this odd number to queue\n            if(nums[j] % 2 != 0): queue.append(j)\n            \n            #If the number of odd numbers in this window exceeds k, then shrink the window from left until the count of odds is not greater than k\n            if(len(queue) > k):\n                while(len(queue) > k):\n                    #If the number at ith index is odd, that means we have to remove this odd number\'s index from queue\n                    if(nums[i] % 2 != 0): queue.popleft()\n                    #Shrink the window from left by incrementing i\n                    i += 1\n            \n            # If number of odd numbers in current window = k\n            # Then total subarrays we can get out of this current window with k odd numbers => (leftmost odd number index - starting of window + 1)\n            if(len(queue) == k): subarrayCount += queue[0] - i + 1\n            \n            #Increase window size from right side\n            j += 1\n            \n        \n        return subarrayCount\n```\n\n# **APPROACH 2 - O(1) SPACE**\nJust remember one thing for such problems where we have to find how many subarrays have "exactly" K something. \n\n\tSubarrays with K something = Subarrays with at most K something - Subarrays with at most K-1 something\n\t\nAt most K means that a subarray should have something <= K. \n\t\nFor this problem, since we have to find subarrays with exactly K odd numbers. That means, \n\t\n\tSubarrays with exactly K odd numbers  = Subarrays with at most K odd numbers  - Subarrays with at most K-1 odd numbers\n\t\nLet me prove it with an example.\n\n\t\tnums = [1,1,2,1,1], k = 3\n\t\t\nSo here, what are the subarrays with <= 3 odd number ? i.e., how many subarrays have at most 3 odd numbers?\n\n\t[1], [1, 1], [1], [1, 1, 2], [1, 2], [2], [1, 1, 2, 1], [1, 2, 1], [2, 1], [1], [1, 2, 1, 1], [2, 1, 1], [1, 1], [1] => 14 Subarrays\n\nNow, lets see how many subarrays have <= 2 odd numbers i.e., <= K- 1 odd numbers\n\t\n\t[1], [1, 1], [1], [1, 1, 2], [1, 2], [2],  [1, 2, 1], [2, 1], [1], [2, 1, 1], [1, 1], [1] => 12 Subarrays\n\t\nSo that means, Subarrays with exactly 3 odd numbers are => 14 - 12 => 2\n\nAnd to prove this, here are all the subarrays with exactly 3 odd numbers\n\t\n\t\t[1,1,2,1] and [1,2,1,1].\n\t\t\nAnd these are the only ones that are not in the list of subarrays with <= 2 odd numbers. \n\nYou can use this template in many similar problems where we are asked to find how many subarrays have exactly K sum, exactly K odd numbers and so on. And there is little to no change you have to make which makes this solution so damn useful.\n\n```\nclass Solution:\n    \n    def atMost(self, nums: List[int], k: int) -> int:\n        \n        countOfSubarrays = 0\n        \n        i,j = 0,0\n        n = len(nums)\n        \n        countOfOdds = 0\n        \n        while j < n:\n            if nums[j] % 2 != 0 : countOfOdds += 1\n                \n            if countOfOdds > k:\n                while countOfOdds > k:\n                    if nums[i] % 2 != 0: countOfOdds -= 1\n                    i += 1\n            \n            countOfSubarrays += j - i + 1\n            j += 1\n        \n        return countOfSubarrays\n        \n    \n    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n        return self.atMost(nums, k) - self.atMost(nums, k-1)\n\n\n```\n
['Sliding Window', 'Python']