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.

Description

4042. Valid K-Unique Subarrays II

Hard69.4% acceptancePremium elsewhere, free here

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[l_i..r_i] is considered valid if:

It contains exactly k distinct numbers, and
Every distinct number in it occurs an even number of times.

For query 0, set l₀ = l0 and r₀ = r0.

Let ans_i denote the result of the i^th query, where ans_i = 1 if nums[l_i..r_i] is valid, and ans_i = 0 otherwise.

For each i > 0, generate the next query as follows:

If ans_i-1 = 1, set g_i-1 = l_i-1 + r_i-1. Otherwise, set g_i-1 = r_i-1 - l_i-1.
Compute l_i = (l_i-1 XOR g_i-1) % n and r_i = (r_i-1 XOR g_i-1) % n.
If l_i > r_i, swap them.

Return a boolean array ans, where ans[i] is true if ans_i = 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`	`[l_i, r_i]`	Subarray	Distinct numbers	Counts	Validity check	`ans[i]`	`[l_i+1, r_i+1]`
0	[1, 2]	[2, 2]	{2} → 1	{2:2}	`false`: The subarray contains fewer than `k` distinct numbers.	`ans₀ = 0`	`g₀ = 2 - 1 = 1 l₁ = (1 XOR 1) % 4 = 0 r₁ = (2 XOR 1) % 4 = 3`
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.	`ans₁ = 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`	`[l_i, r_i]`	Subarray	Distinct numbers	Counts	Validity check	`ans[i]`	`[l_i+1, r_i+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.	`ans₀ = 1`	`g₀ = 2 + 3 = 5 l₁ = (2 XOR 5) % 5 = 7 % 5 = 2 r₁ = (3 XOR 5) % 5 = 6 % 5 = 1` Since `l₁ > r₁`, swap them to obtain `[l₁, r₁] = [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`.	`ans₁ = 0`	-

Thus, ans = [true, false].

Constraints:

2 <= n == nums.length <= 5 × 10⁵
1 <= nums[i] <= 5 × 10⁵
1 <= k <= n
0 <= l₀ < r₀ <= n - 1
1 <= q <= 5 × 10⁵

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

No sample inputs for this problem yet. The examples in the statement show the format.

Your code is saved on this device.