1590. Make Sum Divisible by P - Explanation

Description

You are 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 <= 1,00,000
1 <= nums[i] <= 1,000,000,000
1 <= p <= 1,000,000,000

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Prefix Sums - Used to efficiently compute subarray sums in constant time
Modular Arithmetic - Understanding how remainders work and handling negative modulo results
Hash Maps - Used to store and look up prefix sum remainders for O(1) access

1. Brute Force

Intuition

We need to find the shortest subarray to remove so that the remaining elements sum to a multiple of p. The brute force approach tries every possible subarray length starting from 1. For each length, we slide a window across the array and check if removing that window leaves a sum divisible by p. We return the first (smallest) length l that works.

Algorithm

Compute the total sum of the array. If it is already divisible by p, return 0.
For each possible subarray length l from 1 to n - 1:
- Use a sliding window to compute the sum of each subarray of length l.
- For each window position, calculate the remaining sum (total minus window sum).
- If the remaining sum is divisible by p, return l.
If no valid subarray is found, return -1.

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        n = len(nums)
        totSum = sum(nums)

        if totSum % p == 0:
            return 0

        for l in range(1, n):
            curSum = 0
            for i in range(n):
                curSum += nums[i]
                if i >= l:
                    curSum -= nums[i - l]

                remainSum = totSum - curSum
                if remainSum % p == 0:
                    return l

        return -1

public class Solution {
    public int minSubarray(int[] nums, int p) {
        int n = nums.length;
        long totSum = 0;
        for (int num : nums) totSum += num;

        if (totSum % p == 0) return 0;

        for (int l = 1; l < n; l++) {
            long curSum = 0;
            for (int i = 0; i < n; i++) {
                curSum += nums[i];
                if (i >= l) curSum -= nums[i - l];

                long remainSum = totSum - curSum;
                if (remainSum % p == 0) return l;
            }
        }

        return -1;
    }
}

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        int n = nums.size();
        long long totSum = 0;
        for (int num : nums) totSum += num;

        if (totSum % p == 0) return 0;

        for (int l = 1; l < n; l++) {
            long long curSum = 0;
            for (int i = 0; i < n; i++) {
                curSum += nums[i];
                if (i >= l) curSum -= nums[i - l];

                long long remainSum = totSum - curSum;
                if (remainSum % p == 0) return l;
            }
        }

        return -1;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} p
     * @return {number}
     */
    minSubarray(nums, p) {
        const n = nums.length;
        let totSum = nums.reduce((a, b) => a + b, 0);

        if (totSum % p === 0) return 0;

        for (let l = 1; l < n; l++) {
            let curSum = 0;
            for (let i = 0; i < n; i++) {
                curSum += nums[i];
                if (i >= l) curSum -= nums[i - l];

                const remainSum = totSum - curSum;
                if (remainSum % p === 0) return l;
            }
        }

        return -1;
    }
}

public class Solution {
    public int MinSubarray(int[] nums, int p) {
        int n = nums.Length;
        long totSum = 0;
        foreach (int num in nums) totSum += num;

        if (totSum % p == 0) return 0;

        for (int l = 1; l < n; l++) {
            long curSum = 0;
            for (int i = 0; i < n; i++) {
                curSum += nums[i];
                if (i >= l) curSum -= nums[i - l];

                long remainSum = totSum - curSum;
                if (remainSum % p == 0) return l;
            }
        }

        return -1;
    }
}

func minSubarray(nums []int, p int) int {
    n := len(nums)
    totSum := 0
    for _, num := range nums {
        totSum += num
    }

    if totSum%p == 0 {
        return 0
    }

    for l := 1; l < n; l++ {
        curSum := 0
        for i := 0; i < n; i++ {
            curSum += nums[i]
            if i >= l {
                curSum -= nums[i-l]
            }

            remainSum := totSum - curSum
            if remainSum%p == 0 {
                return l
            }
        }
    }

    return -1
}

class Solution {
    fun minSubarray(nums: IntArray, p: Int): Int {
        val n = nums.size
        var totSum = 0L
        for (num in nums) totSum += num

        if (totSum % p == 0L) return 0

        for (l in 1 until n) {
            var curSum = 0L
            for (i in 0 until n) {
                curSum += nums[i]
                if (i >= l) curSum -= nums[i - l]

                val remainSum = totSum - curSum
                if (remainSum % p == 0L) return l
            }
        }

        return -1
    }
}

class Solution {
    func minSubarray(_ nums: [Int], _ p: Int) -> Int {
        let n = nums.count
        var totSum = 0
        for num in nums {
            totSum += num
        }

        if totSum % p == 0 {
            return 0
        }

        for l in 1..<n {
            var curSum = 0
            for i in 0..<n {
                curSum += nums[i]
                if i >= l {
                    curSum -= nums[i - l]
                }

                let remainSum = totSum - curSum
                if remainSum % p == 0 {
                    return l
                }
            }
        }

        return -1
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Prefix Sum

Intuition

If the total sum has remainder r when divided by p, we need to remove a subarray whose sum also has remainder r (mod p). This transforms the problem into finding the shortest subarray with a specific remainder. Using prefix sums, if the current prefix has remainder curSum, we look for an earlier prefix with remainder (curSum - r + p) % p. A hash map stores the most recent index for each remainder, allowing O(1) lookups.

Algorithm

Calculate the total sum and its remainder remain when divided by p. If remain is 0, return 0.
Initialize a hash map with {0: -1} to handle subarrays starting from index 0.
Iterate through the array, maintaining the running prefix sum modulo p.
For each position, compute the target prefix remainder: (curSum - remain + p) % p.
If this target exists in the map, update the minimum length.
Store the current prefix remainder and its index in the map.
Return the minimum length found, or -1 if no valid subarray exists (or if removing it would leave an empty array).

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total = sum(nums)
        remain = total % p
        if remain == 0:
            return 0

        res = len(nums)
        cur_sum = 0
        remain_to_idx = {0: -1}

        for i, n in enumerate(nums):
            cur_sum = (cur_sum + n) % p
            prefix = (cur_sum - remain + p) % p
            if prefix in remain_to_idx:
                length = i - remain_to_idx[prefix]
                res = min(res, length)
            remain_to_idx[cur_sum] = i

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

public class Solution {
    public int minSubarray(int[] nums, int p) {
        long total = 0;
        for (int num : nums) total += num;
        int remain = (int)(total % p);
        if (remain == 0) return 0;

        int res = nums.length;
        long curSum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);

        for (int i = 0; i < nums.length; i++) {
            curSum = (curSum + nums[i]) % p;
            int prefix = (int)((curSum - remain + p) % p);
            if (map.containsKey(prefix)) {
                res = Math.min(res, i - map.get(prefix));
            }
            map.put((int)curSum, i);
        }

        return res == nums.length ? -1 : res;
    }
}

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        long total = 0;
        for (int num : nums) total += num;
        int remain = total % p;
        if (remain == 0) return 0;

        int res = nums.size();
        long curSum = 0;
        unordered_map<int, int> map;
        map[0] = -1;

        for (int i = 0; i < nums.size(); i++) {
            curSum = (curSum + nums[i]) % p;
            int prefix = (curSum - remain + p) % p;
            if (map.count(prefix)) {
                res = min(res, i - map[prefix]);
            }
            map[curSum] = i;
        }

        return res == nums.size() ? -1 : res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} p
     * @return {number}
     */
    minSubarray(nums, p) {
        let total = nums.reduce((a, b) => a + b, 0);
        let remain = total % p;
        if (remain === 0) return 0;

        let res = nums.length;
        let curSum = 0;
        const map = new Map();
        map.set(0, -1);

        for (let i = 0; i < nums.length; i++) {
            curSum = (curSum + nums[i]) % p;
            let prefix = (curSum - remain + p) % p;
            if (map.has(prefix)) {
                res = Math.min(res, i - map.get(prefix));
            }
            map.set(curSum, i);
        }

        return res === nums.length ? -1 : res;
    }
}

public class Solution {
    public int MinSubarray(int[] nums, int p) {
        long total = 0;
        foreach (int num in nums) total += num;
        int remain = (int)(total % p);
        if (remain == 0) return 0;

        int res = nums.Length;
        long curSum = 0;
        var map = new Dictionary<int, int>();
        map[0] = -1;

        for (int i = 0; i < nums.Length; i++) {
            curSum = (curSum + nums[i]) % p;
            int prefix = (int)((curSum - remain + p) % p);
            if (map.ContainsKey(prefix)) {
                res = Math.Min(res, i - map[prefix]);
            }
            map[(int)curSum] = i;
        }

        return res == nums.Length ? -1 : res;
    }
}

func minSubarray(nums []int, p int) int {
    total := 0
    for _, num := range nums {
        total += num
    }
    remain := total % p
    if remain == 0 {
        return 0
    }

    res := len(nums)
    curSum := 0
    m := make(map[int]int)
    m[0] = -1

    for i, num := range nums {
        curSum = (curSum + num) % p
        prefix := (curSum - remain + p) % p
        if idx, ok := m[prefix]; ok {
            if i-idx < res {
                res = i - idx
            }
        }
        m[curSum] = i
    }

    if res == len(nums) {
        return -1
    }
    return res
}

class Solution {
    fun minSubarray(nums: IntArray, p: Int): Int {
        var total = 0L
        for (num in nums) total += num
        val remain = (total % p).toInt()
        if (remain == 0) return 0

        var res = nums.size
        var curSum = 0L
        val map = HashMap<Int, Int>()
        map[0] = -1

        for (i in nums.indices) {
            curSum = (curSum + nums[i]) % p
            val prefix = ((curSum - remain + p) % p).toInt()
            if (map.containsKey(prefix)) {
                res = minOf(res, i - map[prefix]!!)
            }
            map[curSum.toInt()] = i
        }

        return if (res == nums.size) -1 else res
    }
}

class Solution {
    func minSubarray(_ nums: [Int], _ p: Int) -> Int {
        var total = 0
        for num in nums {
            total += num
        }
        let remain = total % p
        if remain == 0 {
            return 0
        }

        var res = nums.count
        var curSum = 0
        var map = [Int: Int]()
        map[0] = -1

        for i in 0..<nums.count {
            curSum = (curSum + nums[i]) % p
            let prefix = (curSum - remain + p) % p
            if let idx = map[prefix] {
                res = min(res, i - idx)
            }
            map[curSum] = i
        }

        return res == nums.count ? -1 : res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Forgetting to Handle Negative Modulo Results

When computing (curSum - remain) % p, the result can be negative in many programming languages. Always add p before taking modulo: (curSum - remain + p) % p. Failing to do this causes incorrect hash map lookups and wrong answers.

Not Initializing the Hash Map with {0: -1}

The hash map must start with {0: -1} to handle subarrays that start from index 0. Without this initialization, you cannot detect valid subarrays that begin at the first element of the array.

Returning the Wrong Value When No Valid Subarray Exists

If the minimum length found equals n (the entire array), you must return -1 because removing all elements leaves an empty array, which is invalid. A common mistake is forgetting this edge case and returning n instead.