Mixture of array and hash map using prefix sum||70ms Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nnums[0..i] modulo k there are 0,1,...k-1 at most totally k possible for prefix sum (mod
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n`nums[0..i]` modulo k there are 0,1,...k-1 at most totally k possible for prefix sum (mod k).\n\nLook at the constraints `1 <= nums.length <= 10^5, 1 <= p <= 10^9`, it is impossible to use the array for the extreme testcases, although there are possibly very few.\n\nSo, for `p>1e5`, it is to use hash map(unordered_map), but for `p<=10^5` the array method is applied which can run much faster than the one using hash map. \n\nA mixture of array & hash map is done. Python version uses dict.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Define the function `int array_method(int n, int modP, vector<int>& nums, int p)` which uses the similar logic applied for hash map.\n2. in the method `int minSubarray(vector<int>& nums, int p)`, set `n=nums.size()`; using a loop to compute `modP=sum(nums)%p`\n3. When `modP=0`, an early stop for returning `0`.\n4. If `p<=1e5`  proceed the array method; otherwise use `unordered_map<int, int> pos={{0, -1}}` with reserving space.\n5. `len=n`, declare a variable `sumP`\n6.  Use a loop to proceed\n```\nfor(int i=0; i<n; i++){\n    sumP=(sumP+nums[i])%p;// prefix sum sumP=nums[0..i] mod p\n    int y=(sumP-modP+p)%p; // y= sumP-modP mod p\n    if (pos.count(y)) // If prefix sum y is seen at index pos[y]\n        len=min(len, i-pos[y]);//i-pos[y]=length for subarray removed\n    pos[sumP]=i;// update pos with key=sumP last seen index as i\n}\n```\n7. `(len==n)?-1:len` is the answer\n8. The trick for prefix sum with hash map is also applied for solving [Leetcode 523. Continuous Subarray Sum](https://leetcode.com/problems/continuous-subarray-sum/solutions/5277106/mod-k-prefix-sum-hash-table-array-from-mle-to-86ms-beats-99-75/)(In this solution, the whole thinking process for such a kind of questions is presented)\n[Please turn on English subtitles if necessary]\n[https://youtu.be/QSO7-Vh87Os?si=eKFWjfqiRG-HS8pB](https://youtu.be/QSO7-Vh87Os?si=eKFWjfqiRG-HS8pB)\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(\\min(n, p)+n)=O(n)$\n# Code||C++ Mixture of array & hash map 70ms Beats 100% \nIt\'s to mention that the unodered_map version took 80ms beats 99.74% ( the best record)\n```cpp []\nclass Solution {\npublic:\n    static int array_method(int n, int modP, vector<int>& nums, int p){\n        vector<int> pos(p, INT_MAX);\n        pos[0]=-1\n        int len=n, sumP;\n        for(int i=0; i<n; i++){\n            sumP=(sumP+nums[i])%p;\n            int y=(sumP-modP+p)%p;\n            if (pos[y]!=INT_MAX)\n                len=min(len, i-pos[y]);\n            pos[sumP]=i;\n        }\n        return (len==n)?-1:len;\n    }\n    static int minSubarray(vector<int>& nums, int p) {\n        const int n=nums.size();\n        int modP=0;\n        for(int x: nums)\n            modP=(modP+x)%p;\n\n    //    cout<<modP<<endl;\n        if (modP==0) return 0;\n        int sz=min(n, p);\n        if (p<=1e5) return array_method(n, modP, nums, p);\n\n        unordered_map<int, int> pos={{0, -1}};\n        pos.reserve(sz);\n\n        int len=n, sumP=0;\n        for(int i=0; i<n; i++){\n            sumP=(sumP+nums[i])%p;\n            int y=(sumP-modP+p)%p;\n            if (pos.count(y))\n                len=min(len, i-pos[y]);\n            pos[sumP]=i;\n        }\n        return (len==n)?-1:len;\n    }\n};\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# Python version using dict\n```\nclass Solution:\n    def minSubarray(self, nums: List[int], p: int) -> int:\n        n=len(nums)\n        modP=sum(nums)%p\n        if modP==0:  # if total sum is divisible by p\n            return 0\n        \n        pos={0: -1}  # track prefix sum and its index\n        sumP, Len = 0, n\n        \n        for i, x in enumerate(nums):\n            sumP=(sumP+x) % p\n            y=(sumP-modP+p) % p  # find the necessary prefix to remove\n            if y in pos:\n                Len=min(Len, i-pos[y])\n            pos[sumP]=i  # update pos\n        \n        return -1 if Len == n else Len\n\n        \n```
['Array', 'Hash Table', 'Prefix Sum', 'C++', 'Python3']