Prefix sum+Sliding window vs at most k odds||35ms Beats 99.99%
Intuition\n Describe your first thoughts on how to solve this problem. \nThe concept is to use sliding window. With the help of prefix sum, it made an acceptibl
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe concept is to use sliding window. With the help of prefix sum, it made an acceptible solution.\n\n2nd approach usse at most k odds argument which is applied to solve the hard question [992. Subarrays with K Different Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/solutions/4944461/sliding-window-count-subarrays-with-at-most-k-distinct-elements-15ms-beats-99-87/)\n\n3rd C++ is a variant for 1st solution without using prefix sum& a 1 pass solution.\n\nTo make an acceptible solution on weekend is not so comfortable, Some one hates me so strong & downvoted to minus. Why? [see this post](https://leetcode.com/problems/count-number-of-nice-subarrays/solutions/5349423/prefix-sum-sliding-window-vs-at-most-k-odds-35ms-beats-99-99/) \n\n****I never downvote others, try always keeping my mind peaceful to answer the comments from others & not criticize others.****\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Build an 1-indexed prefix sum array `cntOdds` for counting odd numbers in subarrays `nums[0:i]`\n2. Use sliding window pattern to solve like the following. It\'s to see that `cntOdds(nums[l..r])` can be easily computed by using prefix sums\n```\nfor (r=0, l=0; r < n; r++) {\n    // Ensure the current window [l, r] has at least k odd numbers\n    while (l<=r and cntOdds(nums[l..r]) > k) \n        l++;\n\n    // If the current window [l, r] has exactly k odd numbers\n    if (cntOdds(nums[l..r]) == k) {\n        l0 = l;\n        // Count nice subarrays ending at r\n        while (l0 <= r && cntOdds(nums[l0..r]) == k) {\n            cnt++;\n            l0++;\n        }\n    }\n}\n```\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n# Code Prefix sum+Sliding window||C++ 35ms Beats 99.99%\n```\nclass Solution {\npublic:\n    static int numberOfSubarrays(vector<int>& nums, int k) {\n        const int n = nums.size();\n        vector<int> cntOdds(n+1, 0); // 1-indexed prefix sum count of odds\n\n        // Create the prefix sum array\n        for (int i = 0; i < n; i++) \n            cntOdds[i+1] = cntOdds[i] + (nums[i] & 1);\n\n        int l=0, cnt=0;\n        for (int r=0; r < n; r++) {\n            // Ensure the current window [l, r] has at least k odd numbers\n            while (l<=r && cntOdds[r+1] - cntOdds[l] > k) \n                l++;\n\n            // If the current window [l, r] has exactly k odd numbers\n            if (cntOdds[r+1]-cntOdds[l] == k) {\n                int l0 = l;\n                // Count nice subarrays ending at r\n                while (l0 <= r && cntOdds[r+1]-cntOdds[l0] == k) {\n                    cnt++;\n                    l0++;\n                }\n            }\n        }\n        return cnt;\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n\n```\n# Solution using at most k odds\n\nThe solution is a slight modifition for [992. Subarrays with K Different Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/solutions/4944461/sliding-window-count-subarrays-with-at-most-k-distinct-elements-15ms-beats-99-87/) \ncount subarrays with at most K  odd elements. it makes problem  much easier!\n[Please turn on English subtitles if necessary]\n[https://youtu.be/Z113uN6sKDc?si=QvC_REca7V0vt6tW](https://youtu.be/Z113uN6sKDc?si=QvC_REca7V0vt6tW)\nThe following questions can be solved sliding window:\n[713. Subarray Product Less Than K](https://leetcode.com/problems/subarray-product-less-than-k/solutions/4930759/2c-sliding-windows30ms-beats-9992/)\n[2302. Count Subarrays With Score Less Than K](https://leetcode.com/problems/count-subarrays-with-score-less-than-k/solutions/4932340/sliding-windows-like-leetcode-713-44ms-beats-100/)\n[2958. Length of Longest Subarray With at Most K Frequency](https://leetcode.com/problems/length-of-longest-subarray-with-at-most-k-frequency/solutions/4935191/sliding-window-hash-map128ms-beats-9978/)\n[2962. Count Subarrays Where Max Element Appears at Least K Times\n](https://leetcode.com/problems/count-subarrays-where-max-element-appears-at-least-k-times/solutions/4939830/sliding-window-vs-combinatorical-formula-59ms-beats-100/)\n\n\nThese problems can be solved by the following pattern:\n```\nfor(int l,r=0; r<n; r++){\n    do_something_by_adding(nums[r]);\n    while (!check_condition(k)){\n        do_something_by_removing(nums[l]);\n        l++;\n    }\n    update_the_answer();\n}\n```\n# C++ code\n```\nclass Solution {\npublic:\n    int n;\n\n    // Helper function to count subarrays with at most k odd numbers\n    int niceLessEqualK(vector<int>& nums, int k){\n        int odds=0, cnt=0;\n        for(int l=0, r=0; r<n; r++){\n            int x=nums[r];\n            odds+=(x&1);\n            while(odds>k){\n                int y=nums[l];\n                odds-=(y&1);\n                l++;\n            }\n            cnt+=(r-l+1); // # of subarrays ending at r with at most k odd numbers\n        }\n        return cnt;\n    }\n\n    int numberOfSubarrays(vector<int>& nums, int k) {\n        n = nums.size();\n        return niceLessEqualK(nums, k)-niceLessEqualK(nums, k-1);\n    }\n};\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# 3rd C++ sliding window with space O(1) & 1 pass solution\n```\nclass Solution {\npublic:\n    static int numberOfSubarrays(vector<int>& nums, int k) {\n        const int n = nums.size();\n\n        int l=0, cnt=0, odds=0;\n        for (int r=0; r < n; r++) {\n            odds+=(nums[r]&1);\n            // Ensure the current window [l, r] has at least k odd numbers\n            while (l<=r && odds > k){\n                odds-=(nums[l]&1);\n                l++;\n            }\n            // If the current window [l, r] has exactly k odd numbers\n            if (odds== k) {\n                int l0 = l;\n                // Count nice subarrays ending at r\n                while (l0 <= r && (nums[l0]&1)==0) \n                    l0++;\n                cnt+=l0-l+1;\n            }\n        }\n        return cnt;\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['Array', 'Sliding Window', 'Prefix Sum', 'C++']