Count Distinct Subarrays Divisible by K in Sorted Array - Solution & Explanation

Q: Is Count Distinct Subarrays Divisible by K in Sorted Array easy or hard?

The problem is categorized as Hard because it combines two concepts: modular prefix sums and distinct subarray detection. Handling duplicates efficiently while keeping the algorithm within O(n^2) requires careful use of hashing and prefix techniques.

Q: Count Distinct Subarrays Divisible by K in Sorted Array Python/Java solution

Python and Java implementations typically compute prefix sums first, then iterate over all start and end indices. For each valid subarray where sum % k == 0, insert the sequence (or its hash) into a set. The final answer is the size of the set containing unique valid subarrays.

Q: How to solve Count Distinct Subarrays Divisible by K in Sorted Array in O(n)?

An O(n) solution generally does not exist because the number of possible subarrays itself is O(n^2). Even with prefix modulo tricks, you must still verify distinct sequences. The practical improvement focuses on O(n^2) with prefix sums and hashing to keep each check constant time.

Q: What is the best approach for Count Distinct Subarrays Divisible by K in Sorted Array?

The most practical approach uses prefix sums combined with a hash set. Prefix sums allow constant-time calculation of any subarray sum, while the set ensures only distinct subarrays are counted. This reduces the brute force O(n^3) solution to about O(n^2) time with O(n^2) space.

Q: Is Count Distinct Subarrays Divisible by K in Sorted Array asked at Google/Amazon/Meta?

Variants involving prefix sums and modulo arithmetic frequently appear in interviews at companies like Google, Amazon, and Meta. Problems such as counting subarrays divisible by K or detecting equal prefix remainders test understanding of prefix sums and hash maps.

Q: What data structure is used in Count Distinct Subarrays Divisible by K in Sorted Array?

The core data structures are prefix sum arrays and a hash set. Prefix sums provide constant-time range sum queries, while the hash set stores subarray representations or hashes to guarantee distinctness.

Q: What is the time complexity of Count Distinct Subarrays Divisible by K in Sorted Array?

The optimized approach runs in O(n^2) time because every pair of start and end indices may still need to be checked. Prefix sums make each range-sum calculation O(1). Additional space up to O(n^2) can be required to store distinct subarrays or their hashes.

HardArray Hash Table Prefix Sum6 min read

Practice this problem

Problem Statement

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 <= 10⁵
1 <= nums[i] <= 10⁹
nums is sorted in non-descending order.
1 <= k <= 10⁹

Approach Overview

Problem 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.

Solution

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

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

Video Solution

Leetcode 3729 | Count Distinct Subarrays Divisible by K in Sorted Array • CodeWithMeGuys • 660 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Count Distinct Subarrays Divisible by K in Sorted Array easy or hard?

The problem is categorized as Hard because it combines two concepts: modular prefix sums and distinct subarray detection. Handling duplicates efficiently while keeping the algorithm within O(n^2) requires careful use of hashing and prefix techniques.

Count Distinct Subarrays Divisible by K in Sorted Array Python/Java solution

Python and Java implementations typically compute prefix sums first, then iterate over all start and end indices. For each valid subarray where sum % k == 0, insert the sequence (or its hash) into a set. The final answer is the size of the set containing unique valid subarrays.

How to solve Count Distinct Subarrays Divisible by K in Sorted Array in O(n)?

An O(n) solution generally does not exist because the number of possible subarrays itself is O(n^2). Even with prefix modulo tricks, you must still verify distinct sequences. The practical improvement focuses on O(n^2) with prefix sums and hashing to keep each check constant time.

What is the best approach for Count Distinct Subarrays Divisible by K in Sorted Array?

The most practical approach uses prefix sums combined with a hash set. Prefix sums allow constant-time calculation of any subarray sum, while the set ensures only distinct subarrays are counted. This reduces the brute force O(n^3) solution to about O(n^2) time with O(n^2) space.

Is Count Distinct Subarrays Divisible by K in Sorted Array asked at Google/Amazon/Meta?

Variants involving prefix sums and modulo arithmetic frequently appear in interviews at companies like Google, Amazon, and Meta. Problems such as counting subarrays divisible by K or detecting equal prefix remainders test understanding of prefix sums and hash maps.

What data structure is used in Count Distinct Subarrays Divisible by K in Sorted Array?

The core data structures are prefix sum arrays and a hash set. Prefix sums provide constant-time range sum queries, while the hash set stores subarray representations or hashes to guarantee distinctness.

What is the time complexity of Count Distinct Subarrays Divisible by K in Sorted Array?

The optimized approach runs in O(n^2) time because every pair of start and end indices may still need to be checked. Prefix sums make each range-sum calculation O(1). Additional space up to O(n^2) can be required to store distinct subarrays or their hashes.

Ready to solve this problem?

Practice Count Distinct Subarrays Divisible by K in Sorted Array with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyHard

Acceptance27.4%

Approaches1

Reading time6 min