💹Easy 3 Approaches 🔰📊|| Beats 98% || 🚀 Hashing and Two Pointers 🎯|| In Depth
\r\n# Intuition:\r\nThe problem is essentially about finding subarrays with exactly \'k\' odd numbers. \r\nWe can use a hashmap to count the occurrences of pref
\r\n# Intuition:\r\nThe problem is essentially about finding subarrays with exactly \'k\' odd numbers. \r\nWe can use a hashmap to count the occurrences of prefix sums, which helps us keep track \r\nof the number of odd numbers encountered so far.\r\n \r\n# Approach 1:\r\n1. Initialize a hashmap to store the count of prefix sums.\r\n2. Traverse the array and for each element, check if it\'s odd. If it is, increment the current sum.\r\n3. Calculate the difference between the current sum and \'k\'.\r\n4. Check if this difference exists in the hashmap, which means there\'s a subarray with exactly \'k\' odd numbers.\r\n5. Update the hashmap with the current sum.\r\n6. Return the total count of such subarrays.\r\n \r\n# Complexity:\r\n1. Time complexity: O(n), where \'n\' is the length of the input array.\r\n2. Space complexity: O(n), for the hashmap used to store the prefix sums.\r\n\r\n\r\n```JAVA []\r\nclass Solution {\r\n    public int numberOfSubarrays(int[] nums, int k) {\r\n        int n = nums.length; // Get the length of the input array\r\n        HashMap<Integer, Integer> mpp = new HashMap<>(); // Initialize hashmap to store prefix sums\r\n        int sum = 0; // Initialize sum to count odd numbers\r\n        int ans = 0; // Initialize answer to count subarrays with exactly \'k\' odd numbers\r\n        mpp.put(0, 1); // Initialize hashmap with 0 sum to handle cases where subarray starts from index 0\r\n\r\n        for (int i = 0; i < n; i++) { // Iterate through the array\r\n            if (nums[i] % 2 == 1) { // Check if the current number is odd\r\n                sum += 1; // Increment the sum if the number is odd\r\n            }\r\n            int diff = sum - k; // Calculate the difference needed to form a subarray with \'k\' odd numbers\r\n            ans += mpp.getOrDefault(diff, 0); // Add the count of subarrays found with the required difference\r\n            mpp.put(sum, mpp.getOrDefault(sum, 0) + 1); // Update the hashmap with the current sum\r\n        }\r\n        return ans; // Return the total count of subarrays with exactly \'k\' odd numbers\r\n    }\r\n}\r\n```\r\n```C++ []\r\n#include <vector>\r\n#include <unordered_map>\r\n\r\nusing namespace std;\r\n\r\nclass Solution {\r\npublic:\r\n    int numberOfSubarrays(vector<int>& nums, int k) {\r\n        int n = nums.size(); // Get the size of the input array\r\n        unordered_map<int, int> mpp; // Initialize unordered_map to store prefix sums\r\n        int sum = 0; // Initialize sum to count odd numbers\r\n        int ans = 0; // Initialize answer to count subarrays with exactly \'k\' odd numbers\r\n        mpp[0] = 1; // Initialize map with 0 sum to handle cases where subarray starts from index 0\r\n\r\n        for (int i = 0; i < n; ++i) { // Iterate through the array\r\n            if (nums[i] % 2 == 1) { // Check if the current number is odd\r\n                sum += 1; // Increment the sum if the number is odd\r\n            }\r\n            int diff = sum - k; // Calculate the difference needed to form a subarray with \'k\' odd numbers\r\n            ans += mpp[diff]; // Add the count of subarrays found with the required difference\r\n            mpp[sum]++; // Update the map with the current sum\r\n        }\r\n        return ans; // Return the total count of subarrays with exactly \'k\' odd numbers\r\n    }\r\n};\r\n\r\n```\r\n```Python []\r\nclass Solution:\r\n    def numberOfSubarrays(self, nums: list[int], k: int) -> int:\r\n        n = len(nums) # Get the length of the input array\r\n        mpp = {0: 1} # Initialize dictionary to store prefix sums\r\n        sum = 0 # Initialize sum to count odd numbers\r\n        ans = 0 # Initialize answer to count subarrays with exactly \'k\' odd numbers\r\n\r\n        for num in nums: # Iterate through the array\r\n            if num % 2 == 1: # Check if the current number is odd\r\n                sum += 1 # Increment the sum if the number is odd\r\n            diff = sum - k # Calculate the difference needed to form a subarray with \'k\' odd numbers\r\n            ans += mpp.get(diff, 0) # Add the count of subarrays found with the required difference\r\n            mpp[sum] = mpp.get(sum, 0) + 1 # Update the dictionary with the current sum\r\n\r\n        return ans # Return the total count of subarrays with exactly \'k\' odd numbers\r\n\r\n```\r\n\r\n# Intuition\r\n<!-- Describe your first thoughts on how to solve this problem. -->\r\nTo find the number of subarrays with exactly \'k\' odd numbers, we can utilize a sliding window approach combined with prefix sum logic. By counting the number of subarrays with up to \'k\' odd numbers and subtracting the count of subarrays with up to \'k-1\' odd numbers, we can derive the result.\r\n\r\n# Approach 2 \r\n<!-- Describe your approach to solving the problem. -->\r\n1. Implement a helper function `countLessThanEqualToK` that returns the number of subarrays with at most \'k\' odd numbers.\r\n2. The main function will use this helper to calculate the difference between the number of subarrays with at most \'k\' odd numbers and the number of subarrays with at most \'k-1\' odd numbers, giving the result.\r\n3. Use two pointers to maintain a sliding window and keep track of the number of odd numbers in the current window.\r\n4. Expand the window to include new elements and shrink it when the count of odd numbers exceeds \'k\'.\r\n\r\n# Complexity\r\n- Time complexity: $$O(n)$$, where \'n\' is the length of the input array, as each element is processed at most twice (once when expanding and once when contracting the window).\r\n\r\n- Space complexity: $$O(1)$$, as we only use a few extra variables and do not use additional space proportional to the input size.\r\n\r\n```JAVA []\r\n\r\nclass Solution {\r\n    public int numberOfSubarrays(int[] nums, int k) {\r\n        return countLessThanEqualToK(nums, k) - countLessThanEqualToK(nums, k - 1);\r\n    }\r\n\r\n    public int countLessThanEqualToK(int[] nums, int k) {\r\n        int i = 0; // Left pointer of the sliding window\r\n        int count = 0; // Count of valid subarrays\r\n        int oddCount = 0; // Number of odd elements in the current window\r\n        \r\n        for (int j = 0; j < nums.length; j++) { // Right pointer of the sliding window\r\n            if (nums[j] % 2 == 1) // Check if the current element is odd\r\n                oddCount++; // Increment the odd count\r\n            \r\n            // While the number of odd elements exceeds \'k\', move the left pointer to the right\r\n            while (oddCount > k) {\r\n                if (nums[i] % 2 == 1) // Check if the element at the left pointer is odd\r\n                    oddCount--; // Decrement the odd count\r\n                i++; // Move the left pointer to the right\r\n            } \r\n            \r\n            count += j - i + 1; // Add the number of valid subarrays ending at \'j\'\r\n        }\r\n        \r\n        return count; // Return the total count of subarrays with at most \'k\' odd numbers\r\n    }\r\n}\r\n```\r\n```C++ []\r\n#include <vector>\r\nusing namespace std;\r\n\r\nclass Solution {\r\npublic:\r\n    int numberOfSubarrays(vector<int>& nums, int k) {\r\n        return countLessThanEqualToK(nums, k) - countLessThanEqualToK(nums, k - 1);\r\n    }\r\n\r\n    int countLessThanEqualToK(vector<int>& nums, int k) {\r\n        int i = 0; // Left pointer of the sliding window\r\n        int count = 0; // Count of valid subarrays\r\n        int oddCount = 0; // Number of odd elements in the current window\r\n        \r\n        for (int j = 0; j < nums.size(); ++j) { // Right pointer of the sliding window\r\n            if (nums[j] % 2 == 1) // Check if the current element is odd\r\n                oddCount++; // Increment the odd count\r\n            \r\n            // While the number of odd elements exceeds \'k\', move the left pointer to the right\r\n            while (oddCount > k) {\r\n                if (nums[i] % 2 == 1) // Check if the element at the left pointer is odd\r\n                    oddCount--; // Decrement the odd count\r\n                i++; // Move the left pointer to the right\r\n            } \r\n            \r\n            count += j - i + 1; // Add the number of valid subarrays ending at \'j\'\r\n        }\r\n        \r\n        return count; // Return the total count of subarrays with at most \'k\' odd numbers\r\n    }\r\n};\r\n```\r\n```Python []\r\nclass Solution:\r\n    def numberOfSubarrays(self, nums: list[int], k: int) -> int:\r\n        return self.countLessThanEqualToK(nums, k) - self.countLessThanEqualToK(nums, k - 1)\r\n\r\n    def countLessThanEqualToK(self, nums: list[int], k: int) -> int:\r\n        i = 0 # Left pointer of the sliding window\r\n        count = 0 # Count of valid subarrays\r\n        oddCount = 0 # Number of odd elements in the current window\r\n        \r\n        for j in range(len(nums)): # Right pointer of the sliding window\r\n            if nums[j] % 2 == 1: # Check if the current element is odd\r\n                oddCount += 1 # Increment the odd count\r\n            \r\n            # While the number of odd elements exceeds \'k\', move the left pointer to the right\r\n            while oddCount > k:\r\n                if nums[i] % 2 == 1: # Check if the element at the left pointer is odd\r\n                    oddCount -= 1 # Decrement the odd count\r\n                i += 1 # Move the left pointer to the right\r\n            \r\n            count += j - i + 1 # Add the number of valid subarrays ending at \'j\'\r\n        \r\n        return count # Return the total count of subarrays with at most \'k\' odd numbers\r\n```\r\n\r\n# Intuition\r\n<!-- Describe your first thoughts on how to solve this problem. -->\r\nThe problem requires finding subarrays with exactly `k` odd numbers. A useful technique for such problems is the sliding window approach, combined with prefix sums to count the number of valid subarrays.\r\n\r\n# Approach 3\r\n<!-- Describe your approach to solving the problem. -->\r\n1. Initialize an array `map` to keep track of the count of subarrays ending at a specific index with a specific number of odd numbers.\r\n2. Traverse through the array and count the number of odd numbers encountered so far.\r\n3. For each element, calculate the difference between the current count of odd numbers and `k`. This difference tells us how many times we have encountered a prefix with exactly `k` odd numbers.\r\n4. Update the result by adding the count from the `map` for this difference.\r\n5. Finally, update the `map` to include the current count of odd numbers.\r\n\r\n# Complexity\r\n- Time complexity:\r\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\r\n$$O(n)$$ - We traverse the array once.\r\n\r\n- Space complexity:\r\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\r\n$$O(n)$$ - We use an auxiliary array to store counts.\r\n\r\n```JAVA []\r\nclass Solution {\r\n    public int numberOfSubarrays(int[] nums, int k) {\r\n        int n = nums.length;\r\n        int[] map = new int[n + 1]; // create map to store odd count digits\r\n        map[0] = 1; // initialize map[0] for subarrays that exactly match the count k\r\n        int count = 0; // count of odd numbers so far\r\n        int ans = 0; // result to store the number of valid subarrays\r\n        for (int j = 0; j < n; j++) {\r\n            if (nums[j] % 2 == 1) // check if the current number is odd\r\n                count++;\r\n            int diff = count - k; // calculate the difference between count and k\r\n            if (diff >= 0) // if the difference is non-negative, we have valid subarrays\r\n                ans += map[diff]; // add the count of such subarrays to the result\r\n            map[count]++; // update the map with the current count of odd numbers\r\n        }\r\n        return ans; // return the final count of valid subarrays\r\n    }\r\n}\r\n```C++ []\r\nclass Solution {\r\npublic:\r\n    int numberOfSubarrays(vector<int>& nums, int k) {\r\n        int n = nums.size();\r\n        vector<int> map(n + 1, 0); // create map to store odd count digits\r\n        map[0] = 1; // initialize map[0] for subarrays that exactly match the count k\r\n        int count = 0; // count of odd numbers so far\r\n        int ans = 0; // result to store the number of valid subarrays\r\n        for (int j = 0; j < n; j++) {\r\n            if (nums[j] % 2 == 1) // check if the current number is odd\r\n                count++;\r\n            int diff = count - k; // calculate the difference between count and k\r\n            if (diff >= 0) // if the difference is non-negative, we have valid subarrays\r\n                ans += map[diff]; // add the count of such subarrays to the result\r\n            map[count]++; // update the map with the current count of odd numbers\r\n        }\r\n        return ans; // return the final count of valid subarrays\r\n    }\r\n};\r\n\r\n```\r\n```Python []\r\nclass Solution:\r\n    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\r\n        n = len(nums)\r\n        map = [0] * (n + 1)  # create map to store odd count digits\r\n        map[0] = 1  # initialize map[0] for subarrays that exactly match the count k\r\n        count = 0  # count of odd numbers so far\r\n        ans = 0  # result to store the number of valid subarrays\r\n        for num in nums:\r\n            if num % 2 == 1:  # check if the current number is odd\r\n                count += 1\r\n            diff = count - k  # calculate the difference between count and k\r\n            if diff >= 0:  # if the difference is non-negative, we have valid subarrays\r\n                ans += map[diff]  # add the count of such subarrays to the result\r\n            map[count] += 1  # update the map with the current count of odd numbers\r\n        return ans  # return the final count of valid subarrays\r\n\r\n```\r\nPlease UPVote for Anya Chan if you read it till here !!!\r\n![image.png](https://assets.leetcode.com/users/images/1e9043c0-9547-4fd7-80e2-bbc09a47537d_1719040415.06887.png)\r\n\r\n\r\n\r\n
['Array', 'Hash Table', 'Math', 'Sliding Window', 'Python', 'C++', 'Java', 'Python3']