LeetCode 974 - Subarray Sums Divisible by K

LeetCode Problem 974

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Prefix Sum

Solution

Problem Understanding

The problem asks us to count how many non-empty contiguous subarrays have a sum that is divisible by a given integer k.

A subarray is any continuous segment of the array. For example, in the array [1,2,3], the subarrays include [1], [2], [3], [1,2], [2,3], and [1,2,3].

For each possible subarray, we compute its sum. If the sum modulo k equals 0, then that subarray is considered valid. The task is to return the total number of such valid subarrays.

The input consists of:

• nums, an integer array that may contain both positive and negative values
• k, a positive integer divisor

The output is a single integer representing the number of valid subarrays.

The constraints are important because they determine which algorithms are feasible:

• nums.length can be as large as 3 * 10^4
• Each number may be negative
• k can be up to 10^4

A naive solution that checks every subarray individually would require quadratic time, which becomes too slow for arrays of this size.

Negative numbers introduce an additional complication. In many programming languages, the modulo operation with negative values can produce negative remainders. A correct implementation must normalize the remainder so that it always falls in the range [0, k-1].

Several edge cases are especially important:

• Arrays containing negative numbers
• Arrays where many prefix sums produce the same remainder
• Arrays where no valid subarray exists
• Arrays consisting entirely of zeros
• Single-element arrays

The problem guarantees that k >= 2, so division by zero is never an issue.

Approaches

Brute Force Approach

The most direct solution is to examine every possible subarray.

For each starting index i, we expand the subarray to every ending index j >= i, compute the subarray sum, and check whether the sum is divisible by k.

One way to optimize this slightly is to maintain a running sum while expanding the subarray instead of recomputing the sum from scratch each time.

This approach is correct because it explicitly evaluates every possible subarray and counts the valid ones.

However, the number of subarrays in an array of length n is:

$$\frac{n(n+1)}{2}$$

With n = 30000, this becomes far too large. An O(n^2) solution will not pass within time limits.

Optimal Prefix Sum + Hash Map Approach

The key insight comes from prefix sums and modular arithmetic.

Suppose:

• prefixSum[i] is the sum of elements from index 0 through i
• We want the sum of subarray (l...r)

That sum equals:

$$prefixSum[r] - prefixSum[l-1]$$

We want this value to be divisible by k:

$$(prefixSum[r] - prefixSum[l-1]) \mod k = 0$$

Rearranging:

$$prefixSum[r] \mod k = prefixSum[l-1] \mod k$$

This means:

Two prefix sums with the same remainder modulo k define a subarray whose sum is divisible by k.

So instead of checking every subarray directly, we:

• Compute prefix sums incrementally
• Track how many times each remainder has appeared
• Whenever we see the same remainder again, we know additional valid subarrays exist

A hash map is ideal because it allows constant-time lookup and update of remainder frequencies.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every possible subarray
Optimal	O(n)	O(k)	Uses prefix sums and remainder frequency counting

Algorithm Walkthrough

Optimal Algorithm

1. Initialize a hash map called remainder_count.

This map stores how many times each remainder has appeared while processing prefix sums.

We begin with:

remainder_count = {0: 1}

This is extremely important because a prefix sum itself may already be divisible by k. The initial 0:1 represents the empty prefix. 2. Initialize three variables:

• prefix_sum = 0
• result = 0
• remainder_count = {0:1}

3. Iterate through each number in the array.

At each step, add the current number to prefix_sum. 4. Compute the current remainder.

remainder = prefix_sum % k

In Python, % already returns a non-negative remainder.

In languages like Go, we must normalize negative remainders manually. 5. Check whether this remainder has appeared before.

If it has appeared x times, then there are x previous prefix sums with the same remainder.

Each matching prefix sum forms a valid subarray ending at the current position.

So:

result += remainder_count[remainder]

6. Update the frequency map.

After counting the matches, record the current remainder:

remainder_count[remainder] += 1

7. Continue until all elements have been processed.
8. Return result.

Why it works

The algorithm relies on a mathematical property of modular arithmetic.

If two prefix sums have the same remainder when divided by k, then their difference is divisible by k.

Since a subarray sum is the difference between two prefix sums, every pair of equal remainders corresponds to a valid subarray.

The hash map efficiently counts how many compatible prefix sums have already appeared.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        remainder_count = defaultdict(int)
        remainder_count[0] = 1

        prefix_sum = 0
        result = 0

        for num in nums:
            prefix_sum += num

            remainder = prefix_sum % k

            result += remainder_count[remainder]

            remainder_count[remainder] += 1

        return result

The implementation follows the algorithm directly.

We use defaultdict(int) so that missing remainders automatically default to zero frequency.

The initial value remainder_count[0] = 1 accounts for subarrays that begin at index 0.

As we iterate through the array, we continuously update the running prefix sum. The remainder of this prefix sum modulo k determines whether previous compatible prefix sums exist.

Whenever a remainder repeats, we immediately know how many new valid subarrays end at the current index.

Finally, we update the remainder frequency so future iterations can use it.

Go Solution

func subarraysDivByK(nums []int, k int) int {
    remainderCount := make(map[int]int)
    remainderCount[0] = 1

    prefixSum := 0
    result := 0

    for _, num := range nums {
        prefixSum += num

        remainder := prefixSum % k

        if remainder < 0 {
            remainder += k
        }

        result += remainderCount[remainder]

        remainderCount[remainder]++
    }

    return result
}

The Go implementation is structurally identical to the Python version, but there is one important difference involving modulo behavior.

In Go, negative numbers can produce negative remainders. For example:

-2 % 5 == -2

To ensure remainders stay in the valid range [0, k-1], we normalize them:

if remainder < 0 {
    remainder += k
}

Without this correction, equivalent remainders could be treated as different keys in the hash map, producing incorrect results.

Go maps also return the zero value for missing keys automatically, which works well for frequency counting.

Worked Examples

Example 1

Input:

nums = [4,5,0,-2,-3,1]
k = 5

Initial state:

prefix_sum = 0
result = 0
remainder_count = {0:1}

Index	Num	Prefix Sum	Remainder	Previous Count	Result	Updated Map
0	4	4	4	0	0	{0:1, 4:1}
1	5	9	4	1	1	{0:1, 4:2}
2	0	9	4	2	3	{0:1, 4:3}
3	-2	7	2	0	3	{0:1, 4:3, 2:1}
4	-3	4	4	3	6	{0:1, 4:4, 2:1}
5	1	5	0	1	7	{0:2, 4:4, 2:1}

Final answer:

7

Example 2

Input:

nums = [5]
k = 9

Initial state:

prefix_sum = 0
result = 0
remainder_count = {0:1}

Index	Num	Prefix Sum	Remainder	Previous Count	Result	Updated Map
0	5	5	5	0	0	{0:1, 5:1}

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(k)	At most k different remainders are stored

The algorithm performs a constant amount of work per array element, making the runtime linear.

The hash map stores frequencies of remainders modulo k. Since remainders range from 0 to k-1, the map can contain at most k distinct keys.

Test Cases

from typing import List

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        from collections import defaultdict

        remainder_count = defaultdict(int)
        remainder_count[0] = 1

        prefix_sum = 0
        result = 0

        for num in nums:
            prefix_sum += num
            remainder = prefix_sum % k

            result += remainder_count[remainder]
            remainder_count[remainder] += 1

        return result

solution = Solution()

assert solution.subarraysDivByK([4,5,0,-2,-3,1], 5) == 7  # provided example
assert solution.subarraysDivByK([5], 9) == 0  # no valid subarray
assert solution.subarraysDivByK([5], 5) == 1  # single valid element
assert solution.subarraysDivByK([0,0,0], 5) == 6  # all subarrays valid
assert solution.subarraysDivByK([-1,2,9], 2) == 2  # negative values
assert solution.subarraysDivByK([1,2,3,4,5], 3) == 7  # multiple matches
assert solution.subarraysDivByK([1], 2) == 0  # smallest invalid case
assert solution.subarraysDivByK([2,-2,2,-4], 6) == 2  # mixed positive and negative
assert solution.subarraysDivByK([10,20,30], 10) == 6  # every subarray valid
assert solution.subarraysDivByK([1,1,1,1], 2) == 4  # repeated remainder pattern

Test Summary

Test	Why
[4,5,0,-2,-3,1], k=5	Validates the main example
[5], k=9	Ensures zero valid subarrays handled correctly
[5], k=5	Tests single-element valid subarray
[0,0,0], k=5	Every subarray is divisible
[-1,2,9], k=2	Confirms negative number handling
[1,2,3,4,5], k=3	Tests multiple overlapping matches
[1], k=2	Smallest invalid input
[2,-2,2,-4], k=6	Mixed positive and negative values
[10,20,30], k=10	All prefix sums divisible
[1,1,1,1], k=2	Repeated remainder frequencies

Edge Cases

Arrays Containing Negative Numbers

Negative values are a common source of bugs because modulo behavior differs between programming languages.

For example, in Go:

-2 % 5 == -2

If negative remainders are not normalized, logically equivalent remainders may appear as different hash map keys.

The implementation fixes this by converting negative remainders into the range [0, k-1].

Arrays of All Zeros

Consider:

nums = [0,0,0]
k = 5

Every possible subarray sum equals 0, which is divisible by any positive k.

This case stresses whether the algorithm correctly counts repeated remainder matches. Since every prefix sum remainder is 0, the frequency map grows rapidly and generates many valid subarrays.

The implementation handles this naturally through repeated frequency accumulation.

Subarrays Starting at Index Zero

A frequent mistake is forgetting to count subarrays that begin at the start of the array.

For example:

nums = [5]
k = 5

The prefix sum itself is divisible by k.

This is why the hash map starts with:

remainder_count[0] = 1

This initial entry represents an empty prefix sum and ensures such subarrays are counted correctly.