LeetCode 3729 - Count Distinct Subarrays Divisible by K in Sorted Array

The problem asks us to find the number of distinct subarrays in a sorted array nums such that the sum of elements in the subarray is divisible by a given integer k.

leetcodehardarrayhash-tableprefix-sum

LeetCode Problem 3729

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Prefix Sum

Solution

Problem Understanding

The problem asks us to find the number of distinct subarrays in a sorted array nums such that the sum of elements in the subarray is divisible by a given integer k. A subarray is a contiguous segment of the original array, and two subarrays are considered distinct if their sequences of values differ, even if they contain the same numbers in a different arrangement. For example, in [1,1,1], the subarrays [1], [1,1], and [1,1,1] are distinct.

The input is a non-descending sorted array of integers where each integer is positive, and k is a positive integer. The constraints suggest that nums can be very large (up to 10^5 elements) and its values up to 10^9, which means a brute-force approach checking all subarrays is likely too slow. Additionally, duplicates in the array require careful handling to count only distinct sequences.

Important edge cases include arrays with all identical elements, arrays with single elements, and k larger than the sum of any subarray.

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

Approaches

The brute-force approach would generate all possible subarrays, compute their sums, check divisibility by k, and store them in a set to ensure distinctness. While this approach is correct, it is infeasible for the given constraints because generating all subarrays takes O(n^2) time and storing sequences could take O(n^3) space in the worst case.

A more optimal approach leverages prefix sums and modular arithmetic. If we compute the prefix sum of the array and store its modulo k, a subarray from index i to j is divisible by k if (prefix[j+1] - prefix[i]) % k == 0, which is equivalent to prefix[j+1] % k == prefix[i] % k. To handle distinct subarrays, we can use a rolling hash or a Trie/Set of tuples to store sequences efficiently, since the array is sorted and duplicates are contiguous. This reduces unnecessary recomputation and efficiently counts distinct sequences.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(n^3) Generate all subarrays, compute sum, store sequences in set
Optimal O(n^2) O(n^2) Use prefix sums modulo k and a set to store distinct good subarrays; optimized further using rolling hashes if needed

Algorithm Walkthrough

  1. Compute the prefix sum array prefix where prefix[i+1] = prefix[i] + nums[i]. This allows O(1) computation of any subarray sum.
  2. Initialize a set seen to store all distinct good subarrays.
  3. Iterate over all possible start indices i in nums.
  4. For each i, iterate over end indices j >= i.
  5. Compute the sum of the subarray nums[i:j+1] using prefix[j+1] - prefix[i].
  6. Check if this sum is divisible by k.
  7. If divisible, store the tuple (nums[i], nums[i+1], ..., nums[j]) in seen. Using a tuple ensures we track distinct sequences.
  8. After iterating all subarrays, the size of seen is the answer.

Why it works: The prefix sum modulo trick ensures we check divisibility efficiently, while storing sequences as tuples guarantees distinctness. The sorted property allows potential optimizations to skip identical sequences, though this naive optimal approach already handles duplicates correctly.

Python Solution

from typing import List

class Solution:
    def numGoodSubarrays(self, nums: List[int], k: int) -> int:
        prefix = [0] * (len(nums) + 1)
        for i, num in enumerate(nums):
            prefix[i+1] = prefix[i] + num
        
        seen = set()
        n = len(nums)
        
        for i in range(n):
            for j in range(i, n):
                subarray_sum = prefix[j+1] - prefix[i]
                if subarray_sum % k == 0:
                    seen.add(tuple(nums[i:j+1]))
        
        return len(seen)

The Python code follows the algorithm step-by-step. We compute prefix sums for fast subarray sum calculation. A set of tuples ensures only distinct sequences are counted. The double loop iterates over all subarrays, checking divisibility and storing valid ones.

Go Solution

func numGoodSubarrays(nums []int, k int) int64 {
    n := len(nums)
    prefix := make([]int64, n+1)
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i] + int64(nums[i])
    }

    seen := make(map[string]struct{})

    for i := 0; i < n; i++ {
        for j := i; j < n; j++ {
            subSum := prefix[j+1] - prefix[i]
            if subSum % int64(k) == 0 {
                key := ""
                for x := i; x <= j; x++ {
                    key += string(nums[x]) + ","
                }
                seen[key] = struct{}{}
            }
        }
    }

    return int64(len(seen))
}

The Go version mirrors the Python approach. Since Go does not allow slices as map keys directly, we convert each subarray to a string key by joining elements with a delimiter. This ensures uniqueness. We use int64 to handle potential integer overflow.

Worked Examples

Example 1: nums = [1,2,3], k = 3

i j Subarray Sum Sum % k Stored in Seen
0 0 [1] 1 1 No
0 1 [1,2] 3 0 Yes
0 2 [1,2,3] 6 0 Yes
1 1 [2] 2 2 No
1 2 [2,3] 5 2 No
2 2 [3] 3 0 Yes

Answer = 3

Example 2: nums = [2,2,2,2,2,2], k = 6

i j Subarray Sum Sum % k Stored in Seen
0 2 [2,2,2] 6 0 Yes
0 5 [2,2,2,2,2,2] 12 0 Yes

Answer = 2

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) We check all subarrays in a double loop; sum computation is O(1) via prefix sums
Space O(n^2) The set stores tuples of distinct good subarrays; worst case is all subarrays are good and distinct

The complexity can be further improved with rolling hashes or using a Trie to store sequences efficiently instead of using full tuples.

Test Cases

# Provided examples
assert Solution().numGoodSubarrays([1,2,3], 3) == 3  # Example 1
assert Solution().numGoodSubarrays([2,2,2,2,2,2], 6) == 2  # Example 2

# Single element divisible by k
assert Solution().numGoodSubarrays([3], 3) == 1

# Single element not divisible by k
assert Solution().numGoodSubarrays([1], 3) == 0

# All identical elements
assert Solution().numGoodSubarrays([1,1,1,1], 2) == 2  # [1,1], [1,1,1,1]

# Large k larger than sum
assert Solution().numGoodSubarrays([1,2,3], 10) == 0

# Mixed elements
assert Solution().numGoodSubarrays([1,2,2,3,4], 4) == 4
Test Why
[1,2,3], k=3 Standard example with small numbers
[2,2,2,2,2,2], k=6 Checks handling duplicates and distinct subarrays
[3], k=3 Single-element divisible by k
[1], k=3 Single-element not divisible by k
[1,1,1,1], k=2 Multiple identical elements forming distinct sums
[1,2,3], k=10 k larger than any subarray sum, expecting zero
[1,2,2,3,4], k=4 Mixed elements to test various combinations

Edge Cases

Edge Case 1: Single-element array

An array with one element requires checking if the element itself is divisible by k. The implementation handles it naturally since the loop over i and j still works and