Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.
Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.
A subarray is defined as a contiguous block of elements in the array.
Example 1:
Input: nums = [3,1,4,2], p = 6 Output: 1 Explanation: The sum of the elements in nums is 10, which is not divisible by 6. We can remove the subarray [4], and the sum of the remaining elements is 6, which is divisible by 6.
Example 2:
Input: nums = [6,3,5,2], p = 9 Output: 2 Explanation: We cannot remove a single element to get a sum divisible by 9. The best way is to remove the subarray [5,2], leaving us with [6,3] with sum 9.
Example 3:
Input: nums = [1,2,3], p = 3 Output: 0 Explanation: Here the sum is 6. which is already divisible by 3. Thus we do not need to remove anything.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= p <= 109Problem Overview: You are given an integer array nums and an integer p. Remove the smallest contiguous subarray so that the sum of the remaining elements becomes divisible by p. The removed subarray cannot be the entire array.
The key observation: if the total array sum has remainder r = total % p, you must remove a subarray whose sum also has remainder r. The task becomes finding the shortest subarray with that remainder.
Approach 1: Brute Force Subarray Search (O(n²) time, O(1) space)
Check every possible subarray and compute its sum. For each candidate, subtract its sum from the total and verify whether the remaining sum becomes divisible by p. This requires nested loops over the array and repeated modulo checks. While simple to implement, it performs poorly for large inputs because there are O(n²) possible subarrays. Useful only for understanding the problem or verifying small cases.
Approach 2: Prefix Sum and Remainder with HashMap (O(n) time, O(n) space)
Compute prefix sums while tracking each prefix remainder modulo p. Let target = total_sum % p. While iterating, maintain prefix % p and look for a previous prefix remainder that satisfies (current - target) % p. A hash table maps each remainder to its most recent index, allowing constant-time lookup. This transforms the search for a valid removable subarray into a prefix remainder matching problem using prefix sums. The result is the minimum length between matching indices.
The insight: if two prefix sums differ by remainder target modulo p, the subarray between them has exactly the remainder needed to remove.
Approach 3: Sliding Window with Two Pointers (O(n) time, O(1) space)
A two-pointer technique can be applied when reasoning about subarray sums incrementally. Expand the right pointer to accumulate a running sum and shrink from the left when conditions exceed the required remainder window. This approach tries to maintain a candidate window whose sum modulo p matches the required remainder. It avoids extra memory and relies on pointer movement over the array. While less common than the prefix-hash solution, it works when the window behavior can be controlled with modular checks.
Recommended for interviews: The Prefix Sum + HashMap approach is what interviewers expect. It reduces a seemingly complex removal problem into a modular prefix lookup and runs in linear time. Brute force shows you understand the condition, but the prefix remainder trick demonstrates algorithmic maturity.
This approach involves first calculating the remainder of the sum of the given array with respect to p. By maintaining a prefix sum and using the properties of modular arithmetic, we can determine the shortest subarray whose removal results in a remainder of zero.
This implementation calculates the prefix sum and stores remainders in a hashmap. By checking if the target remainder exists in the hashmap, we find the minimal subarray that aligns with our requirement. We update the hashmap with current prefix sums iteratively.
Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(n), for storing prefix sums in the hashmap.
This approach makes use of a sliding window or two-pointer technique to identify the minimal subarray which upon removal makes the sum of the remaining elements divisible by p.
The Java solution uses a HashMap to keep track of prefix sums as keys, linked to their indexes. The final loop computes prefix sums iteratively and checks for the desired remainder, computing the minimal subarray, if applicable.
Java
JavaScript
Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(n), for maintaining the hashmap.
First, we calculate the sum of all elements in the array nums modulo p, denoted as k. If k is 0, it means the sum of all elements in the array nums is a multiple of p, so we directly return 0.
If k is not 0, we need to find the shortest subarray such that removing this subarray makes the sum of the remaining elements modulo p equal to 0.
We can traverse the array nums, maintaining the current prefix sum modulo p, denoted as cur. We use a hash table last to record the last occurrence of each prefix sum modulo p.
If there exists a subarray ending at nums[i] such that removing this subarray makes the sum of the remaining elements modulo p equal to 0, we need to find a previous prefix sum modulo p equal to target at position j such that (target + k - cur) bmod p = 0. If found, we can remove the subarray nums[j+1,..i] to make the sum of the remaining elements modulo p equal to 0.
Therefore, if there exists a target = (cur - k + p) bmod p, we can update the answer to min(ans, i - j). Then, we update last[cur] to i. We continue traversing the array nums until the end to get the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Prefix Sum and Remainder with HashMap | Time Complexity: O(n), where n is the length of nums. |
| Sliding Window with Two Pointers | Time Complexity: O(n), where n is the length of nums. |
| Prefix Sum + Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Check | O(n^2) | O(1) | Small arrays or when explaining the basic idea before optimization |
| Prefix Sum + HashMap | O(n) | O(n) | General case and interview-preferred optimal solution |
| Sliding Window Two Pointers | O(n) | O(1) | When minimizing extra memory and reasoning with window-based sums |
Make Sum Divisible by P | Simplest Explanation | Full Dry Run | Leetcode 1590 | codestorywithMIK • codestorywithMIK • 24,214 views views
Watch 9 more video solutions →Practice Make Sum Divisible by P with our built-in code editor and test cases.
Practice on FleetCode