💡 | O(n) | C++77ms Beats 100.00% | Java, Python | Prefix Sum + HashMap
\n---\n> # Intuition\nThe problem asks us to remove the smallest subarray such that the sum of the remaining elements is divisible by p. We can solve this using
#\n---\n> # Intuition\nThe problem asks us to remove the smallest subarray such that the sum of the remaining elements is divisible by $$p$$. We can solve this using **prefix sums** and a **hashmap** to track remainders. By tracking the cumulative prefix sums modulo $$p$$ and using the properties of modular arithmetic, we can efficiently find the minimum subarray that satisfies the condition.\n\n> # Approach\nTo solve the problem, first compute the total sum of the array modulo $$p$$; if the remainder is $$0$$, no subarray needs to be removed. If not, calculate the prefix sum while tracking remainders in a hashmap. Search for a previous prefix sum that, when subtracted from the current prefix sum, results in a sum divisible by $$p$$. By using a hashmap to store prefix sums and their indices, this can be accomplished in a single pass, allowing us to find the minimum length of the subarray that needs to be removed efficiently.\n\n> # Complexity\n- **Time Complexity** $$O(n)$$, where $$n$$ is the length of the array. We traverse the array once while updating the hashmap.\n- **Space Complexity** $$O(n)$$ for the hashmap storing prefix sums and indices.\n\n\n> # Code\n```cpp []\nclass Solution {\npublic:\n    int minSubarray(vector<int>& nums, int p) {\n        int rem = accumulate(nums.begin(), nums.end(), 0LL) % p, pre = 0, res = nums.size();\n        if (!rem) return 0;\n        unordered_map<int, int> mp = {{0, -1}};\n        for (int i = 0; i < nums.size(); ++i) {\n            pre = (pre + nums[i]) % p;\n            if (mp.count((pre - rem + p) % p)) \n                res = min(res, i - mp[(pre - rem + p) % p]);\n            mp[pre] = i;\n        }\n        return res == nums.size() ? -1 : res;\n    }\n};\nauto io_opt = [] { ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();\n```\n```Java []\nclass Solution {\n    public int minSubarray(int[] nums, int p) {\n        long rem = 0;\n        for (int x : nums) rem = (rem + x) % p;\n        if (rem == 0) return 0;\n        Map<Integer, Integer> mp = new HashMap<>();\n        mp.put(0, -1);\n        long pre = 0;\n        int res = nums.length;\n        for (int i = 0; i < nums.length; ++i) {\n            pre = (pre + nums[i]) % p;\n            if (mp.containsKey((int)((pre - rem + p) % p))) \n                res = Math.min(res, i - mp.get((int)((pre - rem + p) % p)));\n            mp.put((int)pre, i);\n        }\n        return res == nums.length ? -1 : res;\n    }\n}\n```\n```python3 []\nclass Solution:\n    def minSubarray(self, nums: List[int], p: int) -> int:\n        rem = sum(nums) % p\n        if rem == 0:\n            return 0\n        prefix_sum = 0\n        res = len(nums)\n        index_map = {0: -1}\n        for i, num in enumerate(nums):\n            prefix_sum = (prefix_sum + num) % p\n            if (prefix_sum - rem) % p in index_map:\n                res = min(res, i - index_map[(prefix_sum - rem) % p])\n            index_map[prefix_sum] = i\n        return res if res < len(nums) else -1\n```\n\n---\n> **CPP**\n> ![image.png](https://assets.leetcode.com/users/images/13ed6871-7ba8-4a77-8f62-7c7239576ae5_1727927197.589718.png)\n> **Java**\n> ![image.png](https://assets.leetcode.com/users/images/87819c3b-44fe-4544-bcb4-72555c6e1749_1727927208.578076.png)\n> **Python3**\n> ![image.png](https://assets.leetcode.com/users/images/0b927ead-88ca-4702-aafa-1287f22094c1_1727927225.772387.png)\n![Designer.png](https://assets.leetcode.com/users/images/5395952a-4267-4b87-b81f-f28780669704_1726803172.327018.png)\n\n---\n> ### Additional Note\n> **Note**: While the theoretical complexity provides a clear understanding of performance, practical performance can vary based on hardware and input characteristics. Handling remainders efficiently in dynamic situations make sures a consistent time complexity close to **O(n)**.\n\n\n\n---\n\n---\n
['C++', 'Java', 'Python3']