Problem Description

You are given an array of positive integers nums and a positive integer p. Your task is to find and remove the smallest possible subarray (which can be empty) from nums such that the sum of the remaining elements is divisible by p.

A subarray is defined as a contiguous sequence of elements in the array. For example, in [1, 2, 3, 4], [2, 3] is a subarray, but [1, 3] is not.

The key constraints are:

• You cannot remove the entire array (at least one element must remain)
• You want to minimize the length of the removed subarray
• After removal, the sum of remaining elements must be divisible by p (i.e., sum % p == 0)

Return the length of the smallest subarray that needs to be removed. If it's impossible to achieve the goal, return -1.

For example:

• If nums = [3, 1, 4, 2] and p = 6, the sum is 10. Since 10 % 6 = 4, we need to remove a subarray with sum 4 to make the remaining sum divisible by 6. We can remove [4] (length 1), making the remaining elements [3, 1, 2] with sum 6, which is divisible by 6.
• If the original sum is already divisible by p, return 0 (remove an empty subarray).
• If no valid subarray can be removed to achieve the goal, return -1.

Intuition

Let's think about what we're trying to achieve. We have a total sum of the array, and we want to remove a subarray so that the remaining sum is divisible by p.

If the total sum is S and we remove a subarray with sum sub_sum, then the remaining sum is S - sub_sum. For this to be divisible by p, we need: (S - sub_sum) % p = 0

This can be rewritten as: S % p = sub_sum % p

So if S % p = k, we need to find a subarray whose sum modulo p equals k. If k = 0, the array sum is already divisible by p, so we return 0.

Now, how do we efficiently find such a subarray? This is where prefix sums come in handy. If we have prefix sums prefix[i] (sum of first i elements) and prefix[j] (sum of first j elements), then the sum of subarray from index j+1 to i is prefix[i] - prefix[j].

For this subarray sum to have the desired modulo value k, we need: (prefix[i] - prefix[j]) % p = k

Rearranging this equation: prefix[i] % p - prefix[j] % p = k (with proper handling of negative values) prefix[j] % p = (prefix[i] % p - k + p) % p

This means, at each position i, if we know the current prefix sum modulo p (let's call it cur), we need to look for a previous position j where the prefix sum modulo p was target = (cur - k + p) % p.

We can use a hash table to store the last occurrence of each prefix sum modulo value. As we traverse the array, for each position, we check if the required target exists in our hash table. If it does, we've found a valid subarray to remove, and we update our answer with its length. We keep track of the minimum length found.

The beauty of this approach is that we only need one pass through the array, making it efficient with O(n) time complexity.

Learn more about Prefix Sum patterns.

Solution Approach

Let's walk through the implementation step by step:

Step 1: Calculate the remainder First, we calculate k = sum(nums) % p. This tells us what remainder we need to eliminate. If k = 0, the array sum is already divisible by p, so we return 0.

Step 2: Initialize data structures

• We use a hash table last to store the most recent index where each prefix sum modulo p value occurred
• Initialize last = {0: -1} to handle the case where we need to remove a prefix of the array (the -1 index represents the position before the array starts)
• Set cur = 0 to track the current prefix sum modulo p
• Set ans = len(nums) as the initial answer (worst case)

Step 3: Traverse the array For each element at index i with value x:

1. Update current prefix sum: cur = (cur + x) % p This gives us the prefix sum modulo p up to index i.

2. Calculate target: target = (cur - k + p) % p This is the prefix sum modulo value we need to find at some previous position j such that removing the subarray from j+1 to i gives us the desired remainder.

3. Check if target exists: If target is in last:

   • We found a valid subarray to remove: from index last[target] + 1 to i
   • Update answer: ans = min(ans, i - last[target])

4. Update hash table: last[cur] = i Store the current position for this prefix sum modulo value for future lookups.

Step 4: Return result

• If ans == len(nums), it means we couldn't find any valid subarray to remove (the only option would be to remove the entire array, which is not allowed), so return -1
• Otherwise, return ans

Example walkthrough: Let's say nums = [3, 1, 4, 2] and p = 6:

• k = 10 % 6 = 4 (we need to remove a subarray with sum ≡ 4 (mod 6))
• As we traverse:
  • i=0: cur=3, target=(3-4+6)%6=5, not found, last[3]=0
  • i=1: cur=4, target=(4-4+6)%6=0, found at -1, ans=min(4, 1-(-1))=2, last[4]=1
  • i=2: cur=2, target=(2-4+6)%6=4, found at 1, ans=min(2, 2-1)=1, last[2]=2
  • i=3: cur=4, target=(4-4+6)%6=0, found at -1, ans stays 1, last[4]=3
• Return 1 (we can remove the subarray [4] at index 2)

The time complexity is O(n) and space complexity is O(min(n, p)) for the hash table.

Example Walkthrough

Let's work through a concrete example to understand the solution approach.

Example: nums = [6, 3, 5, 2] and p = 9

Step 1: Calculate what we need to remove

• Total sum = 6 + 3 + 5 + 2 = 16
• k = 16 % 9 = 7
• We need to find a subarray whose sum ≡ 7 (mod 9)

Step 2: Initialize

• last = {0: -1} (maps prefix sum mod values to their last seen index)
• cur = 0 (current prefix sum mod p)
• ans = 4 (length of array, worst case)

Step 3: Traverse the array

Index 0 (value = 6):

• Update: cur = (0 + 6) % 9 = 6
• Calculate target: target = (6 - 7 + 9) % 9 = 8
• Check: 8 not in last, so no valid subarray ending here
• Update: last[6] = 0
• State: last = {0: -1, 6: 0}

Index 1 (value = 3):

• Update: cur = (6 + 3) % 9 = 0
• Calculate target: target = (0 - 7 + 9) % 9 = 2
• Check: 2 not in last, so no valid subarray ending here
• Update: last[0] = 1
• State: last = {0: 1, 6: 0}

Index 2 (value = 5):

• Update: cur = (0 + 5) % 9 = 5
• Calculate target: target = (5 - 7 + 9) % 9 = 7
• Check: 7 not in last, so no valid subarray ending here
• Update: last[5] = 2
• State: last = {0: 1, 6: 0, 5: 2}

Index 3 (value = 2):

• Update: cur = (5 + 2) % 9 = 7
• Calculate target: target = (7 - 7 + 9) % 9 = 0
• Check: 0 is in last at index 1!
  • This means removing subarray from index 2 to 3 works
  • Subarray length = 3 - 1 = 2
  • Update: ans = min(4, 2) = 2
• Update: last[7] = 3

Step 4: Return result

• ans = 2, so we return 2

Verification:

• Removing subarray [5, 2] (indices 2-3) leaves us with [6, 3]
• Sum of remaining = 6 + 3 = 9, which is divisible by 9 ✓

The key insight is that we're using modular arithmetic to efficiently find subarrays with specific sum properties, avoiding the need to check all possible subarrays explicitly.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the array nums exactly once using a single for loop with enumerate(nums). Within each iteration, all operations are constant time:

• Computing (cur + x) % p is O(1)
• Computing target = (cur - k + p) % p is O(1)
• Dictionary lookup target in last is O(1) on average
• Dictionary insertion last[cur] = i is O(1) on average
• The min() comparison is O(1)

Additionally, the initial sum(nums) operation takes O(n) time. Therefore, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n)

The algorithm uses a dictionary last to store the mapping between prefix sum remainders and their indices. In the worst case, all prefix sums modulo p are distinct, meaning the dictionary could store up to n + 1 entries (including the initial entry {0: -1}). All other variables (k, cur, ans, target) use constant space. Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Sum Calculation

Pitfall: When calculating sum(nums) % p, the sum might overflow for very large arrays with large values, even though Python handles big integers automatically. In other languages like Java or C++, this is a critical issue.

Solution: Calculate the modulo during the summation process:

total_remainder = 0
for num in nums:
    total_remainder = (total_remainder + num) % p

2. Incorrect Modulo Arithmetic for Negative Values

Pitfall: The expression (current_prefix_sum - total_remainder) % p can be negative, and in some programming languages, negative modulo operations don't behave as expected. Even in Python, forgetting to add p before taking modulo can lead to issues in edge cases.

Wrong approach:

target_prefix_sum = (current_prefix_sum - total_remainder) % p  # Can be negative!

Correct approach:

target_prefix_sum = (current_prefix_sum - total_remainder + p) % p  # Always non-negative

3. Forgetting to Initialize the HashMap with {0: -1}

Pitfall: Not initializing last_seen_index = {0: -1} means you can't handle cases where the subarray to remove starts from index 0 (i.e., removing a prefix of the array).

Example where this matters:

• nums = [1, 2, 3], p = 3
• Total sum = 6, which is divisible by 3
• But if we need to remove a prefix like [1, 2], we need the initial {0: -1} entry

4. Updating HashMap Before Checking

Pitfall: Updating last_seen_index[current_prefix_sum] = index before checking for the target can cause incorrect results when the current position itself could be part of the answer.

Wrong order:

for index, num in enumerate(nums):
    current_prefix_sum = (current_prefix_sum + num) % p
    last_seen_index[current_prefix_sum] = index  # Updated too early!
    target_prefix_sum = (current_prefix_sum - total_remainder + p) % p
    if target_prefix_sum in last_seen_index:
        # This might use the current index incorrectly
        min_length = min(min_length, index - last_seen_index[target_prefix_sum])

Correct order: Always check first, then update.

5. Not Handling the Case Where Only Full Array Removal Works

Pitfall: Forgetting to check if min_length == len(nums) at the end. If the only way to make the sum divisible by p is to remove all elements, we must return -1 since removing the entire array is not allowed.

Missing check:

return min_length  # Wrong! Could return len(nums)

Correct check:

return -1 if min_length == len(nums) else min_length