Valid K-Unique Subarrays II solution and explanation
The problem
You are given an integer array nums of length n and an integer k.
You are also given integers l0 and r0, which define the first query, and an integer q, representing the total number of queries to process.
A subarray nums[li..ri] is considered valid if:
- It contains exactly
kdistinct numbers, and - Every distinct number in it occurs an even number of times.
For query 0, set l0 = l0 and r0 = r0.
Let ansi denote the result of the ith query, where ansi = 1 if nums[li..ri] is valid, and ansi = 0 otherwise.
For each i > 0, generate the next query as follows:
- If
ansi-1 = 1, setgi-1 = li-1 + ri-1. Otherwise, setgi-1 = ri-1 - li-1. - Compute
li = (li-1 XOR gi-1) % nandri = (ri-1 XOR gi-1) % n. - If
li > ri, swap them.
Return a boolean array ans, where ans[i] is true if ansi = 1, and false otherwise.
Example 1:
Input: nums = [1,2,2,1], k = 2, l0 = 1, r0 = 2, q = 2
Output: [false,true]
Explanation:
i |
[li, ri] |
Subarray | Distinct numbers | Counts | Validity check | ans[i] |
[li+1, ri+1] |
|---|---|---|---|---|---|---|---|
| 0 | [1, 2] | [2, 2] | {2} → 1 | {2:2} | false: The subarray contains fewer than k distinct numbers. |
ans0 = 0 |
g0 = 2 - 1 = 1 |
| 1 | [0, 3] | [1, 2, 2, 1] | {1,2} → 2 | {1:2,2:2} | true: The subarray contains exactly k distinct numbers, each occurring an even number of times. |
ans1 = 1 |
- |
Thus, ans = [false, true].
Example 2:
Input: nums = [1,2,3,3,4], k = 1, l0 = 2, r0 = 3, q = 2
Output: [true,false]
Explanation:
i |
[li, ri] |
Subarray | Distinct numbers | Counts | Validity check | ans[i] |
[li+1, ri+1] |
|---|---|---|---|---|---|---|---|
| 0 | [2, 3] | [3, 3] | {3} → 1 | {3:2} | true: The subarray contains exactly k distinct numbers, each occurring an even number of times. |
ans0 = 1 |
g0 = 2 + 3 = 5Since l1 > r1, swap them to obtain [l1, r1] = [1, 2]. |
| 1 | [1, 2] | [2, 3] | {2,3} → 2 | {2:1,3:1} | false: The subarray contains 2 distinct numbers instead of exactly k = 1. |
ans1 = 0 |
- |
Thus, ans = [true, false].
Constraints:
2 <= n == nums.length <= 5 × 1051 <= nums[i] <= 5 × 1051 <= k <= n0 <= l0 < r0 <= n - 11 <= q <= 5 × 105
Approach overview
Problem Overview: Given an integer array and a value k, count the number of contiguous subarrays that contain exactly k distinct elements. This is a classic sliding-window problem that appears in interviews at top tech companies.
Approach 1: Brute Force (O(n²) time, O(k) space)
Enumerate every subarray using two nested loops. For each subarray, insert elements into a set and check if the set size equals k. This approach is straightforward and useful for small arrays but fails for large inputs due to quadratic time.
Approach 2: Sliding Window with At Most K (O(n) time, O(n) space)
The key insight: the count of subarrays with exactly k distinct elements equals atMost(k) - atMost(k-1), where atMost(k) counts subarrays with at most k distinct elements. Implement atMost(k) using two pointers and a frequency map. For each right endpoint, move the left pointer until the window contains at most k distinct numbers, then add right - left + 1 to the total. This is the standard optimal solution, working in linear time and using O(n) space for the map.
Approach 3: Direct Two-Pointer with Frequency Map (O(n) time, O(n) space)
Instead of subtracting counts, directly maintain a window that contains exactly k distinct elements. Use a frequency map and count the number of valid subarrays ending at each position by adjusting the left pointer when the distinct count exceeds k. This avoids the extra atMost function but requires careful handling of when to shrink. It performs the same asymptotically and is purely iterative.
Recommended for interviews: The sliding window with at most k is the preferred approach. It demonstrates a strong understanding of the standard “subarrays with at most K distinct” pattern, which is reusable in many variations (e.g., longest substring with K unique characters). Interviewers expect you to derive this after discarding brute force. Pairing a clear explanation of the subtraction logic with clean code showcases both problem-solving and coding ability.
Master the sliding window technique and hash map usage—these are essential for solving this and similar problems.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n²) | O(k) | Small arrays or when k is tiny |
| Sliding Window (At Most K) | O(n) | O(n) | General case, optimal efficiency |
| Direct Two-Pointer | O(n) | O(n) | When you prefer avoiding the atMost helper |
Frequently asked questions
Is Valid K-Unique Subarrays II easy or hard?
This problem is rated Hard. The brute force is easy, but the optimal sliding window requires the right insight, making it challenging under interview conditions. It is a common follow-up to easier substring counting problems.
Valid K-Unique Subarrays II Python solution?
The Python solution uses a helper function atMost(k) with a dictionary. Iterate right, add to freq, shrink left while len(freq) > k, then add right - left + 1. Finally return atMost(k) - atMost(k-1).
How to solve Valid K-Unique Subarrays II in O(n)?
Use two pointers to maintain a window with at most K distinct elements. Track frequencies in a hash map. For each right pointer, adjust the left pointer until the map size is ≤ K, then add right - left + 1 to the count. Compute atMost(K) and atMost(K-1) and subtract.
What is the best approach for Valid K-Unique Subarrays II?
The sliding window approach that counts subarrays with at most K distinct elements and subtracts atMost(K-1) is the best. It runs in O(n) time and uses O(n) space, making it both efficient and interview-friendly.
Is Valid K-Unique Subarrays II asked at Google/Amazon/Meta?
Yes, this problem is classic and frequently appears in interviews at top companies like Google, Amazon, and Meta. It tests your ability to apply sliding window and hash map patterns under time pressure.
What data structure is used in Valid K-Unique Subarrays II?
A hash map (dictionary) is used to store frequencies of elements inside the current window. It allows O(1) insertion, deletion, and lookups, which is essential for the O(n) sliding window solution.
What is the time complexity of Valid K-Unique Subarrays II?
The optimal solution using sliding window achieves O(n) time complexity, where n is the array length. The space complexity is O(n) in the worst case due to the frequency map.