Watch 10 video solutions for Subarray Sums Divisible by K, a medium level problem involving Array, Hash Table, Prefix Sum. This walkthrough by Pepcoding has 72,963 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [4,5,0,-2,-3,1], k = 5 Output: 7 Explanation: There are 7 subarrays with a sum divisible by k = 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
Example 2:
Input: nums = [5], k = 9 Output: 0
Constraints:
1 <= nums.length <= 3 * 104-104 <= nums[i] <= 1042 <= k <= 104Problem Overview: Given an integer array nums and an integer k, count the number of contiguous subarrays whose sum is divisible by k. The key observation: if two prefix sums leave the same remainder when divided by k, the subarray between them has a sum divisible by k.
Approach 1: Brute Force Subarray Sum (O(n²) time, O(1) space)
Check every possible subarray. Start an index i, then extend the subarray to every j ≥ i while maintaining the running sum. Each time the sum modulo k equals zero, increment the count. This method directly simulates the definition of the problem and helps build intuition about how subarray sums behave. However, the nested iteration over all start and end indices leads to O(n²) time complexity, which becomes slow for large inputs.
Approach 2: Prefix Sums with HashMap (O(n) time, O(k) space)
Use a running prefix sum and track the frequency of remainders prefixSum % k in a hash map. When the same remainder appears again, the subarray between the two indices has a sum divisible by k. For each element, compute the new prefix sum, normalize the remainder using (sum % k + k) % k to handle negative numbers, and check how many times this remainder has appeared before. Add that frequency to the result, then update the map. This transforms the problem into counting matching remainder pairs using a constant‑time hash lookup.
The insight is rooted in prefix sum arithmetic: if prefix[j] % k == prefix[i] % k, then (prefix[j] - prefix[i]) % k == 0, meaning the subarray i+1..j is divisible by k. The hash map stores counts of each remainder so you can accumulate valid subarrays in a single pass.
This solution combines ideas from Prefix Sum, Hash Table, and Array problems. The single linear traversal and constant-time hash operations make it the optimal strategy for large arrays.
Recommended for interviews: Interviewers expect the prefix sum + hash map approach. Brute force demonstrates that you understand subarrays and modular checks, but the O(n) prefix remainder counting technique shows deeper algorithmic thinking and familiarity with common prefix-sum patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Sum | O(n²) | O(1) | Useful for understanding the problem or when constraints are very small |
| Prefix Sum + HashMap | O(n) | O(k) | General case and expected interview solution for large arrays |