[Prefix Sum & Sliding Window Tutorial] Count Number of Nice Subarrays
This post includes the solution for both using Prexis Sum and Sliding Window.\n\nTopic :  Prefix Sum\n\n### Prefix Sum:\nPrefix sum, also known as cumulative su
**This post includes the solution for both using Prexis Sum and Sliding Window.**\n\n**Topic** :  Prefix Sum\n\n### Prefix Sum:\nPrefix sum, also known as cumulative sum, is a technique used in computer science and mathematics to efficiently calculate the sum of a sequence of numbers. The prefix sum of a sequence `a[0], a[1] ... a[n - 1]` is another sequence` s[0], s[1] ... s[n - 1]` where each element `s[i]` represent the sum of the first i elements of the original array. (ChatGPT)\n\nAn example of prefix sum array:\n`a = [1, 2, 3, 4, 5]` =>\n`s = [1, 3, 6, 10, 15]`\n\nFeel free to refer to these two tutorials on prefix sums and their applications:\n* [Subarray Sums Divisible by K](https://leetcode.com/problems/subarray-sums-divisible-by-k/solutions/5281785/prefix-sum-number-theory-hash-table-tutorial-subarray-sums-divisible-by-k/)\n* [Continuous Subarray Sum](https://leetcode.com/problems/continuous-subarray-sum/solutions/5278327/prefix-sum-number-theory-hash-table-tutorial-continuous-subarray-sum/)\n\n\n___\n\n# **Solution**:\nTo solve this problem, we may use the **prefix sum** skill.\n\nWe first take the modulus of each `nums[i]` by two for `0 <= i < len(nums)`. Odd numbers will result in `1`, while even numbers will result in `0`. The problem becomes finding the number of subarrays that sum to `k` with the modified `nums` array.\n\nWe begin by computing the prefix sum for each index `i` of the provided array `nums`. \n\nWith the given example `nums = [1, 1, 2, 1, 1]` and `k = 3`, here is the running prefix sum : `p = [1, 2, 2, 3, 4]`. \n\nNote that the sum of a subarray `nums[i] + nums[i + 1] + ... nums[j]` can be represented as `p[j] - (i > 0 ? p[i - 1] : 0)`. \n\nIf a subarray `nums[i] + nums[i + 1] + ... + nums[j]` equals k, it must satisfy:\n* `p[j] - (i > 0 ? p[i - 1] : 0) == k`\n\nWe can utilize a **Hash Table** `prefixCount` to store our prefix sums frequency, where each key represents a prefix sum value and its corresponding occurrences. Using a native array will be faster in this case because it avoids the overhead of key hashing typically required by hash tables.\n\nFor the current running `j`, we find the number of `p[i]` satisfy the above condition. We increase the answer by `prefixCounnt[p[i]]`. \nIn this context, `p[i]` is computed as `p[j] - k`, under the condition that `p[j] >= k`. We initialize `prefixCount[0]` to `1` to specifically address the scenario where `p[j]` equals `k`.\n\n\n```c++ []\nclass Solution {\npublic:\n    int numberOfSubarrays(vector<int>& nums, int k) {\n        for(int i = 0; i < nums.size(); i++) {\n            nums[i] %= 2;\n        }\n        \n        vector<int> prefixCounnt(nums.size() + 1);\n        prefixCounnt[0] = 1;\n        int s = 0, ans = 0;\n        for(int i = 0; i < nums.size(); i++) {\n            s += nums[i];\n            ans += (s >= k) ? prefixCounnt[s - k] : 0;\n            prefixCounnt[s]++;\n        }\n        return ans;\n    }\n};\n```\n```java []\nclass Solution {\n    public int numberOfSubarrays(int[] nums, int k) {\n        for (int i = 0; i < nums.length; i++) {\n            nums[i] %= 2;\n        }\n        \n        int[] prefixCount = new int[nums.length + 1];\n        prefixCount[0] = 1;\n        int s = 0;\n        int ans = 0;\n        \n        for (int num : nums) {\n            s += num;\n            if (s >= k) {\n                ans += prefixCount[s - k];\n            }\n            prefixCount[s]++;\n        }\n        \n        return ans;\n    }\n}\n```\n```python []\nclass Solution:\n    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n        for i in range(len(nums)):\n            nums[i] %= 2\n        \n        prefix_count = [0] * (len(nums) + 1)\n        prefix_count[0] = 1\n        s = 0\n        ans = 0\n        \n        for num in nums:\n            s += num\n            if s >= k:\n                ans += prefix_count[s - k]\n            prefix_count[s] += 1\n        \n        return ans\n```\n```Go []\nfunc numberOfSubarrays(nums []int, k int) int {\n    for i := 0; i < len(nums); i++ {\n        nums[i] %= 2\n    }\n    \n    prefixCount := make([]int, len(nums)+1)\n    prefixCount[0] = 1\n    s := 0\n    ans := 0\n    \n    for _, num := range nums {\n        s += num\n        if s >= k {\n            ans += prefixCount[s-k]\n        }\n        prefixCount[s]++\n    }\n    \n    return ans\n}\n```\n```PHP []\nclass Solution {\n\n    /**\n     * @param Integer[] $nums\n     * @param Integer $k\n     * @return Integer\n     */\n    function numberOfSubarrays($nums, $k) {\n        foreach ($nums as $key => $value) {\n            $nums[$key] %= 2;\n        }\n        \n        $prefixCount = array_fill(0, count($nums) + 1, 0);\n        $prefixCount[0] = 1;\n        $s = 0;\n        $ans = 0;\n        \n        foreach ($nums as $num) {\n            $s += $num;\n            if ($s >= $k) {\n                $ans += $prefixCount[$s - $k];\n            }\n            $prefixCount[$s]++;\n        }\n        \n        return $ans;\n    }\n}\n```\n```javascript []\n/**\n * @param {number[]} nums\n * @param {number} k\n * @return {number}\n */\nvar numberOfSubarrays = function(nums, k) {\n    for (let i = 0; i < nums.length; i++) {\n        nums[i] %= 2;\n    }\n    \n    let prefixCount = new Array(nums.length + 1).fill(0);\n    prefixCount[0] = 1;\n    let s = 0;\n    let ans = 0;\n    \n    for (let num of nums) {\n        s += num;\n        if (s >= k) {\n            ans += prefixCount[s - k];\n        }\n        prefixCount[s]++;\n    }\n    \n    return ans;\n};\n```\n\n\n**Complexity:**\n* Time Complexity : `O(n)`.\n* Space Complexity : `O(n)`.\n\n<br/><br/>\n___\n\n\n**Topic** :  Sliding Window\nSliding Window problems are problems in which a fixed or variable-size window is moved through a data structure, typically an array or string, to solve problems efficiently based on continuous subsets of elements. This technique is used when we need to find subarrays or substrings according to a given set of conditions. (GFG Reference)\n\nThere are two types of sliding window:\n- Fixed Size Sliding Window\n- Dynamic Size Sliding Window\n\n___\n\n## Dynamic Size Sliding Window\nA **Dynamic Size Sliding Window** refers to a window or subarray whose size is not fixed; instead, it dynamically expands or shrinks based on whether it meets specified conditions.\n\n## Intuition Behind Dynamic Size Sliding Window\nGenerally, questions involving sliding window techniques often inquire about the number of subarrays or substrings that satisfy specific conditions.\n\nBy using brute force, we enumerate all subarrays or substrings and check whether each satisfies the condition. This enumeration typically results in at least `O(n^2)` time complexity.\n\nFor a fixed variable L, we check all subarrays [L : R] where L \u2264 R. The sliding window technique can be applied when all subarrays [L : M] satisfy the condition, and all subarrays with a left bound \'L\' and any right bound [M + 1 : R] fail the condition.\n\nLet\'s assume our current window has the range `[L : R]`. If the subarray `[L : R + 1]` satisfies the condition, we can continue expanding the right pointer `R` to find the maximum `M` for the current fixed `L`. If `[L : R + 1]` fails the condition, there is no need to check `[L : R + n]` because all subsequent subarrays will also fail the condition. Now it is time to expand the left pointer.\n\n## Solution\nFirst, it\'s essential to determine whether the sliding window technique is applicable. This method is suitable when:\n```\nFor a fixed variable L, we check all subarrays [L : R] where L \u2264 R. The sliding window technique can be applied when all subarrays [L : M] satisfy the condition, and all subarrays with a left bound \'L\' and any right bound [M + 1 : R] fail the condition.\n```\nThis question satisfies these criteria, making it suitable for applying the sliding window technique. How? \n\n```\nThe number of subarrays with exactly  `k`  odd numbers equals the count of \nsubarrays with at most `k` odd numbers minus the count of subarrays with at most `k - 1` odd numbers.\n```\n\nWe can define an `atMost(k)` function to determine the number of subarrays that have at most `k` odd numbers. We initialized a left pointer `j` and a right pointer `i`, with `i` continuously moving to the right until the condition fails. We use `s` to count the number of odd numbers within our window. If `s > k`, it indicates that the window fails the condition, prompting us to move the left pointer and update `s` accordingly. \n\nAt the same time, for the window `[j : i]` with the fixed right pointer `i`, there are `i - j + 1` subarrays that satisfy the condition.\n\n\n\n<br/><br/>\n\n\n```c++ []\nclass Solution {\npublic:\n    int numberOfSubarrays(vector<int>& nums, int k) {\n        return atMost(nums, k) - atMost(nums, k - 1); \n    }\n    \n    int atMost(vector<int>& nums, int k) {\n        int s = 0, ans = 0;\n        for(int i = 0, j = 0; i < nums.size(); i++) {\n            s += nums[i] % 2;\n            while(s > k) s -= (nums[j++] % 2);\n            ans += (i - j + 1);\n        }\n        return ans;\n    }\n};\n```\n```java []\nclass Solution {\n    public int numberOfSubarrays(int[] nums, int k) {\n        return atMost(nums, k) - atMost(nums, k - 1);\n    }\n    \n    private int atMost(int[] nums, int k) {\n        int s = 0, ans = 0;\n        for (int i = 0, j = 0; i < nums.length; i++) {\n            s += nums[i] % 2;\n            while (s > k) {\n                s -= nums[j++] % 2;\n            }\n            ans += (i - j + 1);\n        }\n        return ans;\n    }\n}\n```\n```python []\nclass Solution:\n    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n        return self.atMost(nums, k) - self.atMost(nums, k - 1)\n    \n    def atMost(self, nums: List[int], k: int) -> int:\n        s, ans = 0, 0\n        j = 0\n        for i in range(len(nums)):\n            s += nums[i] % 2\n            while s > k:\n                s -= nums[j] % 2\n                j += 1\n            ans += (i - j + 1)\n        return ans\n```\n```Go []\nfunc atMost(nums []int, k int) int {\n    s, ans := 0, 0\n    j := 0\n    for i := 0; i < len(nums); i++ {\n        s += nums[i] % 2\n        for s > k {\n            s -= nums[j] % 2\n            j++\n        }\n        ans += (i - j + 1)\n    }\n    return ans\n}\n\nfunc numberOfSubarrays(nums []int, k int) int {\n    return atMost(nums, k) - atMost(nums, k-1)\n}\n```\n```PHP []\nclass Solution {\n\n    /**\n     * @param Integer[] $nums\n     * @param Integer $k\n     * @return Integer\n     */\n    function atMost($nums, $k) {\n        $s = 0;\n        $ans = 0;\n        $j = 0;\n        for ($i = 0; $i < count($nums); $i++) {\n            $s += $nums[$i] % 2;\n            while ($s > $k) {\n                $s -= $nums[$j++] % 2;\n            }\n            $ans += ($i - $j + 1);\n        }\n        return $ans;\n    }\n    \n    function numberOfSubarrays($nums, $k) {\n        return $this->atMost($nums, $k) - $this->atMost($nums, $k - 1);\n    }\n}\n```\n```javascript []\n/**\n * @param {number[]} nums\n * @param {number} k\n * @return {number}\n */\nvar numberOfSubarrays = function(nums, k) {\n    function atMost(nums, k) {\n        let s = 0, ans = 0;\n        let j = 0;\n        for (let i = 0; i < nums.length; i++) {\n            s += nums[i] % 2;\n            while (s > k) {\n                s -= nums[j++] % 2;\n            }\n            ans += (i - j + 1);\n        }\n        return ans;\n    }\n    \n    return atMost(nums, k) - atMost(nums, k - 1);\n};\n```\n\n\n**Complexity**:\n* Time Complexity : `O(n)`\n* Space Complexity : `O(1)`\n\n\n\n**Feel free to leave a comment if something is confusing, or if you have any suggestions on how I can improve the post.**
['Array', 'Hash Table', 'C', 'PHP', 'Prefix Sum', 'Java', 'Go', 'Python3', 'JavaScript']