K Divisible Elements Subarrays solution and explanation
9 more videos on this problem
K Divisible Elements Subarrays | Leetcode 2261 | Maps | Contest 291 🔥🔥Coding Decoded · 7:04 · 4K views
2261 K Divisible Elements Subarrays Leetcode|Leetcode Weekly 291 contestAshutosh sharma · 9:12 · 1K views
2261. K Divisible Elements Subarrays (Leetcode Medium)Programming Live with Larry · 13:39 · 1K views
Weekly Leetcode Contest 291 | 6049. K Divisible Elements SubarrayscodingMohan · 17:38 · 1K views
【每日一题】LeetCode 2261. K Divisible Elements SubarraysHuifeng Guan · 27:38 · 539 views
Leetcode Weekly-contest-291 - K Divisible Elements SubarraysPrakhar Agrawal · 5:05 · 388 views
How to solve K divisible elements subarrays leetcode - Leetcode weekly contest - Leetcode MediumTHE CODE CLUB · 5:09 · 234 views
LeetCode 2261 k divisible elements subarrays[CE] Code Engineering · 14:07 · 178 views
LEETCODE wweekly-contest-291| C | 2261. K Divisible Elements Subarrays | 24.12.23CodingVerse · 6:30 · 109 views
K Divisible Elements Subarrays | LeetCode 2261PH · 10:43 · 16 views
The problem
Given an integer array nums and two integers k and p, return the number of distinct subarrays, which have at most k elements that are divisible by p.
Two arrays nums1 and nums2 are said to be distinct if:
- They are of different lengths, or
- There exists at least one index
iwherenums1[i] != nums2[i].
A subarray is defined as a non-empty contiguous sequence of elements in an array.
Example 1:
Input: nums = [2,3,3,2,2], k = 2, p = 2 Output: 11 Explanation: The elements at indices 0, 3, and 4 are divisible by p = 2. The 11 distinct subarrays which have at most k = 2 elements divisible by 2 are: [2], [2,3], [2,3,3], [2,3,3,2], [3], [3,3], [3,3,2], [3,3,2,2], [3,2], [3,2,2], and [2,2]. Note that the subarrays [2] and [3] occur more than once in nums, but they should each be counted only once. The subarray [2,3,3,2,2] should not be counted because it has 3 elements that are divisible by 2.
Example 2:
Input: nums = [1,2,3,4], k = 4, p = 1 Output: 10 Explanation: All element of nums are divisible by p = 1. Also, every subarray of nums will have at most 4 elements that are divisible by 1. Since all subarrays are distinct, the total number of subarrays satisfying all the constraints is 10.
Constraints:
1 <= nums.length <= 2001 <= nums[i], p <= 2001 <= k <= nums.length
Follow up:
Can you solve this problem in O(n2) time complexity?
Approach overview
Problem Overview: Given an integer array nums, an integer k, and p, count the number of distinct subarrays where at most k elements are divisible by p. Two subarrays are considered the same if their sequences of values are identical.
The challenge has two parts: enforcing the constraint on divisible elements and ensuring only unique subarrays are counted. Straight enumeration works, but you must track uniqueness efficiently using hashing or a trie.
Approach 1: Brute Force with Set for Distinctions (O(n^2 * L) time, O(n^2) space)
Enumerate every possible subarray starting at index i. As you extend the subarray to the right, maintain a counter of numbers divisible by p. Once the counter exceeds k, stop extending that start index because any longer subarray will also violate the constraint. Each valid subarray is inserted into a hash set (typically as a tuple or encoded string) so duplicates are removed automatically.
This approach relies heavily on a array traversal and a hash table to track uniqueness. The main cost comes from storing and hashing subarray representations, which can take up to O(L) per insertion where L is the subarray length. Despite the quadratic enumeration, the early break when divisible elements exceed k prunes many cases.
Approach 2: Optimized Sliding Window with HashMap (O(n^2) time, O(n^2) space)
A more efficient implementation avoids repeatedly rebuilding subarray representations. Use a sliding expansion from each start index while maintaining the count of numbers divisible by p. Instead of storing raw subarrays, compute an incremental rolling hash for each extension and insert the hash into a set or hashmap.
Each time the window grows by one element, update the hash value using a polynomial rolling hash formula. This avoids copying the entire subarray and keeps insertion close to constant time. The window stops expanding once the divisible count exceeds k. Because hashes represent subarrays uniquely with very high probability, duplicates are filtered efficiently.
This approach combines enumeration with hashing techniques similar to substring problems. It leverages ideas from hash tables and structures like a trie, which can also store subarray prefixes without duplication.
Recommended for interviews: Start with the brute-force enumeration to show you understand how to enforce the k divisible constraint. Interviewers typically expect you to optimize the uniqueness check using hashing (or a trie). The optimized hashing approach demonstrates stronger algorithmic thinking and reduces overhead from repeatedly copying subarrays.
Approach 1: Brute Force with Set for Distinctions
In this approach, we generate all possible subarrays of the input array using two nested loops. For each subarray, we count the number of elements divisible by `p`. If the count is less than or equal to `k`, we add the subarray as a tuple to a set to ensure distinctness. Finally, the size of the set gives us the required count of distinct subarrays.
def countDistinct(nums, k, p):
distinct_subarrays = set()
n = len(nums)
for i in range(n):
divisible_count = 0
subarray = []
for j in range(i, n):
subarray.append(nums[j])
if nums[j] % p == 0:
divisible_count += 1
if divisible_count <= k:
distinct_subarrays.add(tuple(subarray))
else:
break
return len(distinct_subarrays)import java.util.*;
public class Solution {
public int countDistinct(int[] nums, int k, int p) {
Set<String> distinctSubarrays = new HashSet<>();
int n = nums.length;
for (int i = 0; i < n; ++i) {
int divisibleCount = 0;
StringBuilder subarray = new StringBuilder();
for (int j = i; j < n; ++j) {
subarray.append(nums[j]).append(",");
if (nums[j] % p == 0) {
divisibleCount++;
}
if (divisibleCount <= k) {
distinctSubarrays.add(subarray.toString());
} else {
break;
}
}
}
return distinctSubarrays.size();
}
}#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
int countDistinct(vector<int>& nums, int k, int p) {
unordered_set<string> distinctSubarrays;
int n = nums.size();
for (int i = 0; i < n; ++i) {
int divisibleCount = 0;
string subarray;
for (int j = i; j < n; ++j) {
subarray += to_string(nums[j]) + ",";
if (nums[j] % p == 0) {
divisibleCount++;
}
if (divisibleCount <= k) {
distinctSubarrays.insert(subarray);
} else {
break;
}
}
}
return distinctSubarrays.size();
}function countDistinct(nums, k, p) {
let distinctSubarrays = new Set();
for (let i = 0; i < nums.length; i++) {
let divisibleCount = 0;
let subarray = [];
for (let j = i; j < nums.length; j++) {
subarray.push(nums[j]);
if (nums[j] % p === 0) {
divisibleCount++;
}
if (divisibleCount <= k) {
distinctSubarrays.add(subarray.toString());
} else {
break;
}
}
}
return distinctSubarrays.size;
}using System;
using System.Collections.Generic;
public class Solution {
public int CountDistinct(int[] nums, int k, int p) {
HashSet<string> distinctSubarrays = new HashSet<string>();
int n = nums.Length;
for (int i = 0; i < n; ++i) {
int divisibleCount = 0;
string subarray = "";
for (int j = i; j < n; ++j) {
subarray += nums[j].ToString() + ",";
if (nums[j] % p == 0) {
divisibleCount++;
}
if (divisibleCount <= k) {
distinctSubarrays.Add(subarray);
} else {
break;
}
}
}
return distinctSubarrays.Count;
}
}This solution uses two nested loops to generate all subarrays and counts the number of elements divisible by p. A set is used to store each subarray uniquely.
Time Complexity: O(n^3) due to nested loops and set operations.
Space Complexity: O(n^2) due to the storage of subarrays in the set.
Approach 2: Optimized Sliding Window with HashMap
This approach optimizes the subarray generation process using a sliding window technique. We utilize a hashmap to keep track of subarray counts, efficiently managing the addition and removal of elements to/from the subarray as we slide the window.
def countDistinct(nums, k, p):
distinct_subarrays = set()
n = len(nums)
for start in range(n):
divisible_elements = 0
subarray = []
for end in range(start, n):
subarray.append(nums[end])
if nums[end] % p == 0:
divisible_elements += 1
if divisible_elements > k:
break
distinct_subarrays.add(tuple(subarray))
return len(distinct_subarrays)import java.util.*;
public class Solution {
public int countDistinct(int[] nums, int k, int p) {
Set<String> distinctSubarrays = new HashSet<>();
int n = nums.length;
for (int start = 0; start < n; ++start) {
int divisibleCount = 0;
StringBuilder subarray = new StringBuilder();
for (int end = start; end < n; ++end) {
subarray.append(nums[end]).append(",");
if (nums[end] % p == 0) {
divisibleCount++;
}
if (divisibleCount > k) {
break;
}
distinctSubarrays.add(subarray.toString());
}
}
return distinctSubarrays.size();
}
}#include <vector>
#include <unordered_set>
#include <string>
using namespace std;
int countDistinct(vector<int>& nums, int k, int p) {
unordered_set<string> distinctSubarrays;
int n = nums.size();
for (int start = 0; start < n; ++start) {
int divisibleCount = 0;
string subarray;
for (int end = start; end < n; ++end) {
subarray += to_string(nums[end]) + ",";
if (nums[end] % p == 0) {
divisibleCount++;
}
if (divisibleCount > k) {
break;
}
distinctSubarrays.insert(subarray);
}
}
return distinctSubarrays.size();
}function countDistinct(nums, k, p) {
let distinctSubarrays = new Set();
let n = nums.length;
for (let start = 0; start < n; start++) {
let divisibleCount = 0;
let subarray = [];
for (let end = start; end < n; end++) {
subarray.push(nums[end]);
if (nums[end] % p === 0) {
divisibleCount++;
}
if (divisibleCount > k) break;
distinctSubarrays.add(subarray.toString());
}
}
return distinctSubarrays.size;
}using System;
using System.Collections.Generic;
public class Solution {
public int CountDistinct(int[] nums, int k, int p) {
HashSet<string> distinctSubarrays = new HashSet<string>();
int n = nums.Length;
for (int start = 0; start < n; ++start) {
int divisibleCount = 0;
string subarray = "";
for (int end = start; end < n; ++end) {
subarray += nums[end].ToString() + ",";
if (nums[end] % p == 0) {
divisibleCount++;
}
if (divisibleCount > k) {
break;
}
distinctSubarrays.Add(subarray);
}
}
return distinctSubarrays.Count;
}
}The optimized sliding window approach generates subarrays by extending one end while counting divisible elements with adjustable starting points, skipping further extensions if conditions are not met.
Time Complexity: O(n^2) since subarrays are handled more efficiently compared to the brute-force approach.
Space Complexity: O(n^2) for distinct subarray storage in sets.
Approach 3: Enumeration + String Hashing
We can enumerate the left endpoint i of the subarray, and then enumerate the right endpoint j in the range [i, n). During the enumeration of the right endpoint, we use double hashing to store the hash value of the subarray into a set. Finally, we return the size of the set.
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the array.
function countDistinct(nums: number[], k: number, p: number): number {
const s = new Set<bigint>();
const [base1, base2] = [131, 13331];
const [mod1, mod2] = [1000000007, 1000000009];
for (let i = 0; i < nums.length; i++) {
let [h1, h2, cnt] = [0, 0, 0];
for (let j = i; j < nums.length; j++) {
if (nums[j] % p === 0) {
cnt++;
if (cnt > k) {
break;
}
}
h1 = (h1 * base1 + nums[j]) % mod1;
h2 = (h2 * base2 + nums[j]) % mod2;
s.add((BigInt(h1) << 32n) | BigInt(h2));
}
}
return s.size;
}func countDistinct(nums []int, k int, p int) int {
s := map[int]bool{}
base1, base2 := 131, 13331
mod1, mod2 := 1000000007, 1000000009
for i := range nums {
h1, h2, cnt := 0, 0, 0
for j := i; j < len(nums); j++ {
if nums[j]%p == 0 {
cnt++
if cnt > k {
break
}
}
h1 = (h1*base1 + nums[j]) % mod1
h2 = (h2*base2 + nums[j]) % mod2
s[h1<<32|h2] = true
}
}
return len(s)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force with Set for Distinctions | Time Complexity: O(n^3) due to nested loops and set operations. Space Complexity: O(n^2) due to the storage of subarrays in the set. |
| Optimized Sliding Window with HashMap | Time Complexity: O(n^2) since subarrays are handled more efficiently compared to the brute-force approach. Space Complexity: O(n^2) for distinct subarray storage in sets. |
| Enumeration + String Hashing | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Set for Distinctions | O(n^2 * L) | O(n^2) | Simple implementation when constraints are moderate and clarity is preferred |
| Optimized Sliding Window with HashMap (Rolling Hash) | O(n^2) | O(n^2) | Best practical approach to reduce subarray copying and speed up uniqueness checks |
Frequently asked questions
Is K Divisible Elements Subarrays easy or hard?
K Divisible Elements Subarrays is generally rated Medium. The enumeration idea is straightforward, but handling distinct subarrays efficiently requires hashing or trie techniques, which adds algorithmic complexity.
How to solve K Divisible Elements Subarrays in O(n)?
An O(n) solution is not feasible because the number of distinct subarrays itself can reach O(n^2). The best achievable complexity enumerates subarrays with early stopping when more than k elements are divisible by p, resulting in O(n^2) time.
What is the best approach for K Divisible Elements Subarrays?
The most practical solution enumerates subarrays while tracking the count of elements divisible by p and stores each valid subarray using a rolling hash in a set. This avoids copying full subarrays and ensures uniqueness efficiently. The overall complexity is O(n^2) time and O(n^2) space.
What data structure is used in K Divisible Elements Subarrays?
The main data structures are a hash set or hashmap to store unique subarrays (often via rolling hash values). Some implementations also use a trie to store subarray prefixes without duplication, though hashing is more common in interview solutions.
What is the time complexity of K Divisible Elements Subarrays?
The optimized approach runs in O(n^2) time because every starting index may expand up to n positions. Hashing allows constant‑time uniqueness checks. Space complexity is O(n^2) in the worst case to store distinct subarray hashes.
K Divisible Elements Subarrays Python or Java solution approach?
Both Python and Java implementations follow the same idea: iterate over each start index, track how many elements are divisible by p, compute a rolling hash for the growing subarray, and insert it into a set to count unique results.
Is K Divisible Elements Subarrays asked at Google, Amazon, or Meta?
This problem reflects common interview patterns involving subarray enumeration, hashing, and constraint tracking. Variants of the problem appear in interviews at large tech companies where candidates must combine array traversal with hash‑based deduplication.