Make Sum Divisible by P — Prefix Mod With a Hashmap

Problem Statement#

Given an array of positive integers nums and a positive integer p, remove the smallest subarray so the sum of the remaining elements is divisible by p. You cannot remove the entire array. Return the length of the smallest such subarray, or -1 if impossible.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= p <= 10^9

Input:  nums = [3,1,4,2], p = 6
Output: 1

Input:  nums = [6,3,5,2], p = 9
Output: 2

Why This Problem Matters#

LeetCode 1590 is a Google, Amazon, and Microsoft favorite that combines two hashmap interview staples: prefix sums and modular arithmetic. It is the harder cousin of "subarray sum equals K" and forces candidates to reason about residues rather than raw sums.

The reason interviewers love it: the brute-force O(n^2) solution is easy to write, but the optimal O(n) solution requires fluency with (a - b) mod p and the discipline to keep a hashmap of last-seen prefix residues. The latter is exactly the level of hash table FAANG fluency a senior engineer is expected to demonstrate.

It also tests a subtle gotcha: the modulus of negative numbers. In Python the language handles it; in JavaScript, Java, and C++ you must add p and take mod again.

The Core Insight#

Let total = sum(nums) and target = total % p. If target == 0, the answer is 0. Otherwise we need the shortest subarray whose sum has residue target modulo p. Equivalently, for prefix sums pref[i] we need the shortest i, j with (pref[j] - pref[i]) % p == target, which rearranges to pref[i] % p == (pref[j] - target) % p.

Walk the array left to right. For each prefix residue cur, look up whether (cur - target) mod p has been seen, and if so update the best length.

Visual Dry Run#

nums = [3,1,4,2], p = 6. total = 10, target = 10 % 6 = 4.

Best valid length = 1 — remove [4].

Solution (Optimal)#

class Solution:
    def minSubarray(self, nums: list[int], p: int) -> int:
        target = sum(nums) % p
        if target == 0:
            return 0
        last = {0: -1}
        cur = 0
        best = len(nums)
        for j, v in enumerate(nums):
            cur = (cur + v) % p
            need = (cur - target) % p
            if need in last:
                best = min(best, j - last[need])
            last[cur] = j
        return best if best < len(nums) else -1

var minSubarray = function(nums, p) {
    const total = nums.reduce((a, b) => a + b, 0);
    const target = total % p;
    if (target === 0) return 0;
    const last = new Map();
    last.set(0, -1);
    let cur = 0;
    let best = nums.length;
    for (let j = 0; j < nums.length; j++) {
        cur = (cur + nums[j]) % p;
        const need = ((cur - target) % p + p) % p;
        if (last.has(need)) {
            best = Math.min(best, j - last.get(need));
        }
        last.set(cur, j);
    }
    return best < nums.length ? best : -1;
};

Time: O(n) — single pass with O(1) hashmap operations. Space: O(min(n, p)) — at most n distinct residues are stored.

Common Mistakes#

• Forgetting the (... + p) % p trick in languages where % returns negative values for negative operands.
• Returning the answer when the whole array would need to be removed; the problem forbids that.
• Initializing the map without 0 -> -1, which loses subarrays that start at index 0.
• Not handling total % p == 0 early; the answer is 0, not 1.
• Storing the first occurrence of each residue instead of the last; we need the most recent index for the shortest window.

Interview Tips#

• State the algebraic transformation early: "I want a window with residue equal to target."
• Walk through the negative-mod gotcha to demonstrate language awareness.
• Mention the last map stores the most recent index because we want the shortest window.
• Trace one example end to end; this builds interviewer confidence in your edge-case handling.

Follow-up Questions#

• What if nums can contain negative values? Hint: same algorithm; rely on the (x % p + p) % p adjustment.
• What if you must return the actual subarray? Hint: store (index, residue) and reconstruct from the matching pair.
• What if you need the longest such subarray? Hint: store the earliest occurrence of each residue.
• What if you need to make the sum divisible by both p and q? Hint: use the LCM of p and q.
• Can you solve it in O(1) extra space when p is small? Hint: yes; use an array indexed by residue.

Key Takeaways#

• LeetCode 1590 is a hash table FAANG favorite at Google, Amazon, and Microsoft.
• Reduce the problem to "shortest window with a given residue" using target = total % p.
• Initialize the map with {0: -1} to allow the empty prefix.
• Store the latest index per residue to minimize window length.
• Always defend against negative mods: ((x - target) % p + p) % p.
• Handle the trivial target == 0 case before entering the loop.
• Time is O(n), space is O(min(n, p)) — optimal for this problem class.