You are given an integer array nums sorted in non-descending order and a positive integer k.
A subarray of nums is good if the sum of its elements is divisible by k.
Return an integer denoting the number of distinct good subarrays of nums.
Subarrays are distinct if their sequences of values are. For example, there are 3 distinct subarrays in [1, 1, 1], namely [1], [1, 1], and [1, 1, 1].
Example 1:
Input: nums = [1,2,3], k = 3
Output: 3
Explanation:
The good subarrays are [1, 2], [3], and [1, 2, 3]. For example, [1, 2, 3] is good because the sum of its elements is 1 + 2 + 3 = 6, and 6 % k = 6 % 3 = 0.
Example 2:
Input: nums = [2,2,2,2,2,2], k = 6
Output: 2
Explanation:
The good subarrays are [2, 2, 2] and [2, 2, 2, 2, 2, 2]. For example, [2, 2, 2] is good because the sum of its elements is 2 + 2 + 2 = 6, and 6 % k = 6 % 6 = 0.
Note that [2, 2, 2] is counted only once.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109nums is sorted in non-descending order.1 <= k <= 109Problem Overview: Given a sorted array, count how many distinct subarrays have a sum divisible by k. Two conditions must hold: the subarray sum % k equals zero, and the subarray sequence has not appeared before.
Approach 1: Brute Force Enumeration with Set (O(n^3) time, O(n^2) space)
Generate every possible subarray using two nested loops for the start and end index. Compute the sum of each subarray directly and check sum % k == 0. If the condition holds, store the subarray (for example as a tuple or string) inside a hash set to ensure uniqueness. Because the array is sorted, duplicate values often produce identical subarrays, so the set removes repeated sequences automatically. The drawback is the extra loop needed to recompute sums, leading to O(n^3) time.
Approach 2: Prefix Sum + Hash Set for Distinct Subarrays (O(n^2) time, O(n^2) space)
Precompute a prefixSum array so any subarray sum can be calculated in constant time. For indices i and j, compute the sum using prefix[j+1] - prefix[i]. If the result is divisible by k, build a representation of the subarray and store it in a hash set to enforce distinctness. This eliminates repeated summation and reduces the runtime to O(n^2). The hash set still stores up to O(n^2) unique subarrays in the worst case.
Approach 3: Prefix Modulo Buckets + Rolling Hash (O(n^2) time, O(n) space typical)
Track prefix sums modulo k. If two prefixes share the same remainder, the subarray between them has a sum divisible by k. Instead of constructing full subarray objects repeatedly, compute a polynomial rolling hash for the subarray using precomputed powers. Insert each valid subarray hash into a set to keep only distinct sequences. This approach leverages prefix sum remainder matching while using a hash table to deduplicate efficiently. The sorted property of the array helps ensure repeated sequences generate identical hashes consistently.
Recommended for interviews: Prefix sum with hashing is the expected direction. Start by explaining the brute force enumeration to show baseline reasoning, then optimize using prefixSum for constant-time range queries. Combining this with a hash-based deduplication strategy demonstrates strong understanding of array traversal and modular arithmetic patterns.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration with Set | O(n^3) | O(n^2) | Useful for understanding the problem and validating correctness on small inputs |
| Prefix Sum + Hash Set | O(n^2) | O(n^2) | General solution when you need fast range-sum queries and distinct subarray tracking |
| Prefix Modulo Buckets + Rolling Hash | O(n^2) | O(n) typical | Preferred when avoiding large subarray objects and improving hashing efficiency |
Leetcode 3729 | Count Distinct Subarrays Divisible by K in Sorted Array • CodeWithMeGuys • 625 views views
Watch 1 more video solutions →Practice Count Distinct Subarrays Divisible by K in Sorted Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor