⚡Flashcard Drill➔
NeetCode #112LC-974MediumArrays & Hashing
← Back to All Problems

#112 · #974 · Subarray Sums Divisible by K(和可被 K 整除的子数组)

📌 Problem Statement & Constraints

Given an integer array nums and an integer k, return the number of non-empty subarrays whose sum is divisible by k. Constraints: 1 <= nums.length <= 2 * 10^4, -10^4 <= nums[i] <= 10^4, 2 <= k <= 10^4.

💡 Core Algorithmic Approaches

  1. A subarray sum nums[i..j] is divisible by k exactly when the two prefix sums P[j+1] and P[i] are congruent modulo k.
  2. So count, for each residue, how many earlier prefixes shared it. Each such pair contributes one valid subarray.
  3. Maintain a hash map from residue to count, seeded with {0: 1} to represent the empty prefix.
  4. Python's % always returns a non-negative result for a positive modulus, which conveniently normalises negative prefix sums.

💻 Benchmark Python3 Implementation

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        from collections import defaultdict
        cnt = defaultdict(int)
        cnt[0] = 1                         # the empty prefix has residue 0
        cur = 0
        res = 0
        for x in nums:
            cur = (cur + x) % k            # Python's % is non-negative for k > 0
            res += cnt[cur]                # pair with every earlier equal residue
            cnt[cur] += 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass with O(1) average hash operations.
💾 Space Complexity
O(min(n, k)) for the residue counts.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting cnt[0] = 1: subarrays starting at index 0 would be missed.
  • Worrying about negative residues: in Python -7 % 5 == 3, so the residues are already normalised. In C++/Java you would need ((cur % k) + k) % k.
  • Using a sliding window: it fails because the values may be negative, so the prefix sums are not monotone.
  • Storing a set of residues rather than counts: two different start indices with the same residue each yield a distinct subarray, so multiplicities matter.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems