Valid K-Unique Subarrays I - Solution & Explanation

Q: Is Valid K-Unique Subarrays I easy or hard?

This problem is rated Hard on LeetCode. It requires a solid understanding of the sliding window technique and the ability to transform an 'exactly K' problem into an 'at most K' problem. While the concept is straightforward, implementation details can be tricky, making it a challenging interview question.

Q: Valid K-Unique Subarrays I Python/Java solution

In Python, use a defaultdict or Counter to maintain frequencies. In Java, use a HashMap . The core logic is identical: expand the right pointer, update the map, shrink the left pointer when the map size exceeds k, and accumulate the count. Both implementations run in O(n) time.

HardArray Bit Manipulation Hash Function Prefix Sum4 min read

Practice this problem

Problem Statement

You are given an integer array nums and an integer k.

You are also given a 2D integer array queries, where queries[i] = [l_i, r_i] represents the subarray nums[l_i..r_i].

For each query, the subarray nums[l_i..r_i] is considered valid if:

It contains exactly k distinct numbers, and
The frequency of every number in the subarray is even.

Return a boolean array ans, where ans[i] is true if nums[l_i..r_i] is valid, and false otherwise.

Example 1:

Input: nums = [1,2,2,1], k = 2, queries = [[0,1],[0,3],[1,2]]

Output: [false,true,false]

Explanation:

`i`	`[l_i, r_i]`	Subarray	Unique numbers	Frequency	Validity check
0	[0, 1]	[1, 2]	{1, 2} → 2	{1: 1, 2: 1}	`false`: Element counts are not even.
1	[0, 3]	[1, 2, 2, 1]	{1, 2} → 2	{1: 2, 2: 2}	`true`: Exactly `k = 2` distinct elements, all appear an even number of times.
2	[1, 2]	[2, 2]	{2} → 1	{2: 2}	`false`: Number of distinct elements is less than `k = 2`.

Thus, ans = [false, true, false].

Example 2:

Input: nums = [3,3,3], k = 1, queries = [[1,2],[0,2]]

Output: [true,false]

Explanation:

`i`	`[l_i, r_i]`	Subarray	Unique numbers	Frequency	Validity check
0	[1, 2]	[3, 3]	{3} → 1	{3: 2}	`true`: Exactly `k = 1` distinct element, appears an even number of times.
1	[0, 2]	[3, 3, 3]	{3} → 1	{3: 3}	`false`: 3 does not appear an even number of times.

Thus, ans = [true, false].

Constraints:

2 <= n == nums.length <= 10⁵
1 <= nums[i] <= 10⁵
1 <= k <= n
1 <= queries.length <= 10⁵
queries[i] == [l_i, r_i]
0 <= l_i < r_i <= n - 1

Approach Overview

Problem Overview: Given an integer array nums and an integer k, return the number of subarrays that contain exactly k distinct values. This is a classic sliding window problem where you need to count contiguous subarrays with a fixed number of unique elements.

Approach 1: Brute Force (O(n²) time, O(n) space)

Iterate over every possible subarray using two nested loops. For each starting index, expand the ending index while maintaining a frequency map. After each expansion, check if the number of distinct keys equals k; if so, increment the counter. This approach is straightforward but inefficient for large inputs because it explores all subarrays, leading to quadratic time complexity.

Approach 2: Sliding Window with At Most K (O(n) time, O(k) space)

The key insight is that the number of subarrays with exactly k distinct elements equals subarraysWithAtMostK(k) - subarraysWithAtMostK(k-1). Implement a helper function that counts subarrays with at most k distinct elements using a sliding window. Expand the right pointer, add the new element to a frequency map, and if the map size exceeds k, shrink the left pointer until the size is ≤ k. For each valid window, add right - left + 1 to the count. This runs in O(n) because each element is processed at most twice (once when added, once when removed).

Approach 3: Direct Sliding Window with Two Pointers (O(n) time, O(k) space)

For a direct solution, maintain two pointers left and right and a frequency map. Expand right and add the element. If the number of distinct elements exceeds k, move left forward and decrement frequencies until the count drops to k. Then, count all subarrays ending at right that have exactly k distinct elements by using a helper to find the minimum left index that still gives exactly k distinct elements. This approach is more complex but avoids the subtraction trick. However, the subtraction method is cleaner and equally efficient.

Recommended for interviews: The optimal solution is the sliding window with the at-most-k subtraction technique. It demonstrates a deep understanding of the sliding window pattern and reduces the problem to a simpler subproblem. Brute force shows you understand the problem but fails on constraints. The optimal approach is expected in interviews at top companies like Google, Amazon, and Meta.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute Force	O(n²)	O(n)	Only for very small inputs or educational purposes
Sliding Window (At Most K)	O(n)	O(k)	Optimal for most cases, especially when k is small
Direct Sliding Window	O(n)	O(k)	When you need to avoid the subtraction trick or want a single-pass solution

Video Solution

Beat My Solution: LeetCode 4033's Valid K-Unique Subarrays I (Hard)

Ethano1:1826 views

Frequently Asked Questions

Is Valid K-Unique Subarrays I easy or hard?

This problem is rated Hard on LeetCode. It requires a solid understanding of the sliding window technique and the ability to transform an 'exactly K' problem into an 'at most K' problem. While the concept is straightforward, implementation details can be tricky, making it a challenging interview question.

Valid K-Unique Subarrays I Python/Java solution

In Python, use a defaultdict or Counter to maintain frequencies. In Java, use a HashMap<Integer, Integer>. The core logic is identical: expand the right pointer, update the map, shrink the left pointer when the map size exceeds k, and accumulate the count. Both implementations run in O(n) time.

How to solve Valid K-Unique Subarrays I in O(n)?

Use the sliding window pattern. Define a helper function that counts subarrays with at most k distinct elements. Then compute exactly k as f(k) - f(k-1). The helper expands the right pointer, maintains a frequency map, and shrinks the left pointer when the distinct count exceeds k, adding right-left+1 to the count for each valid window.

What is the best approach for Valid K-Unique Subarrays I?

The best approach is the sliding window technique with the 'at most K' subtraction trick. It runs in O(n) time and O(k) space, making it optimal for large arrays. This method is widely accepted in interviews and competitive programming.

Is Valid K-Unique Subarrays I asked at Google/Amazon/Meta?

Yes, this problem is a classic sliding window question that frequently appears in interviews at top tech companies like Google, Amazon, and Meta. It tests your ability to handle subarray counting with constraints on distinct elements, a common pattern in real-world scenarios.

What data structure is used in Valid K-Unique Subarrays I?

A hash map (or dictionary) is used to store the frequency of each element in the current window. This allows O(1) updates and checks for the number of distinct elements. The sliding window itself is implemented with two pointers.

What is the time complexity of Valid K-Unique Subarrays I?

The optimal sliding window solution runs in O(n) time, where n is the length of the input array. Each element is added and removed from the frequency map at most once, leading to linear time complexity. Space complexity is O(k) for the frequency map.

Ready to solve this problem?

Practice Valid K-Unique Subarrays I with our built-in code editor and test cases.

Practice on FleetCode

Valid K-Unique Subarrays II

Problem Info

DifficultyHard

Acceptance34.8%

Approaches0

Reading time4 min