Python | Hash Map & Sliding Window
see the Successfully Accepted Submission\n\n# Code\npython3 []\nclass Solution:\n    def minSubarray(self, nums: List[int], p: int) -> int:\n        # Step 1: C
[see the Successfully Accepted Submission](https://leetcode.com/problems/make-sum-divisible-by-p/submissions/1410009813/?envType=daily-question&envId=2024-10-03)\n\n# Code\n```python3 []\nclass Solution:\n    def minSubarray(self, nums: List[int], p: int) -> int:\n        # Step 1: Calculate total sum and the remainder that needs to be removed\n        total_sum = sum(nums)\n        target_remainder = total_sum % p\n        \n        # If the total sum is already divisible by p, no need to remove anything\n        if target_remainder == 0:\n            return 0\n        \n        # Step 2: Initialize variables\n        prefix_sum = 0\n        min_length = len(nums)\n        remainder_map = {0: -1}  # This is used to store the mod value of prefix sums\n        \n        # Step 3: Traverse the array\n        for i, num in enumerate(nums):\n            prefix_sum = (prefix_sum + num) % p\n            # Calculate the mod of the required prefix sum to find the subarray\n            needed_remainder = (prefix_sum - target_remainder) % p\n            \n            if needed_remainder in remainder_map:\n                min_length = min(min_length, i - remainder_map[needed_remainder])\n            \n            # Update the map with the current prefix_sum mod p and index\n            remainder_map[prefix_sum] = i\n        \n        # Step 4: If no valid subarray was found, return -1\n        return min_length if min_length < len(nums) else -1\n\n```\n\n## Observations:\n\n### 1. **Initial Sum Modulo**:\n   First, calculate the total sum of the array. If this sum is already divisible by `p`, then the answer is `0` because we don\u2019t need to remove any elements.\n\n### 2. **Required Remainder**:\n   If the total sum is not divisible by `p`, we need to remove a subarray such that the sum of the remaining elements becomes divisible by `p`. The difference between the total sum and the largest multiple of `p` gives us a "target remainder" that we need to "cancel out" by removing a subarray.\n\n### 3. **Prefix Sum and Hash Map**:\n   The problem can be approached using a **prefix sum** technique. We use the modulo operation to track the remainder of the prefix sum as we iterate through the array. A key insight is that if two prefix sums have the same remainder when divided by `p`, the subarray between these two points has a sum divisible by `p`.\n\n   To efficiently find the smallest subarray, we can maintain a hash map that stores the remainder and the index of the prefix sum. Then, at each index, we can check if a previous prefix sum would allow us to remove a subarray that achieves the desired sum.\n\n## Steps:\n\n1. **Calculate the total sum** of the array and the target remainder.\n2. Use a **prefix sum** and a **hash map** to store the mod `p` values as you iterate through the array.\n3. For each prefix sum, check if removing the subarray from a previous matching remainder can give the desired result.\n4. Return the length of the smallest valid subarray found.\n\n## Explanation of the Code:\n\n### 1. **total_sum**:\n   We first calculate the sum of the entire array and compute the remainder when divided by `p`.\n\n### 2. **target_remainder**:\n   This is the value we need to "cancel out" by removing a subarray so that the remaining sum becomes divisible by `p`.\n\n### 3. **prefix_sum and remainder_map**:\n   - As we iterate through the array, we keep track of the cumulative sum modulo `p`.\n   - We store each prefix sum mod `p` in a hash map, where the key is the remainder and the value is the index where this remainder was last seen.\n\n### 4. **needed_remainder**:\n   - For each index `i`, we calculate the remainder that would need to have been seen earlier in order to remove a subarray that achieves the desired sum. If such a remainder was seen, we compute the length of the potential subarray and update the minimum length if necessary.\n\n### 5. **Return**:\n   - If we find a valid subarray, return its length. Otherwise, return `-1` if no valid subarray exists.\n\n## Time Complexity:\n- **O(n)**, where `n` is the length of the array, because we traverse the array once and perform constant-time operations for each element.\n\n## Space Complexity:\n- **O(n)**, because we store the prefix sums and their indices in the hash map.\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']