_1248. Count Number of Nice Subarrays.md

1248. Count Number of Nice Subarrays

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 21, 2024

Last updated : July 20, 2024

---

Related Topics : Array, Hash Table, Math, Sliding Window

Acceptance Rate : 71.15 %

---

Solutions

• m1248 Daily v1.py
• m1248 Daily v2 Single Pass.py

Python

m1248 Daily v1.py

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        oddCounter = 0
        remainders = [0] * len(nums)
        for i in range(len(nums)) :
            if nums[i] % 2 == 1 :
                oddCounter += 1
                remainders[i] = 1

            nums[i] = oddCounter

        left, right = 0, 0

        counter = 0
        visited = set()
        toVisit = deque([(0, 0)])
        while toVisit :
            left, right = toVisit.popleft()

            if left >= len(nums) or right >= len(nums) :
                continue
            if (left, right) in visited :
                continue
            visited.add((left, right))

            odds = nums[right] - nums[left] + remainders[left]
            if odds == k :
                counter += 1
                toVisit.append((left + 1, right))
                toVisit.append((left, right + 1))
            
            elif odds < k :
                toVisit.append((left, right + 1))
            
            else :
                toVisit.append((left + 1, right))
        return counter

m1248 Daily v2 Single Pass.py

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        oddCounter = 0
        output = 0
        
        sumTracker = defaultdict(int)
        sumTracker[0] = 1

        for num in nums :
            oddCounter += num % 2

            pairedValue = oddCounter - k
            if pairedValue in sumTracker :
                output += sumTracker[pairedValue]

            sumTracker[oddCounter] = sumTracker[oddCounter] + 1

        return output