Skip to content

4033. Valid K-Unique Subarrays I

Description

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

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

For each query, the subarray nums[li..ri] 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[li..ri] 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 [li, ri] 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 [li, ri] 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 <= 105
  • 1 <= nums[i] <= 105
  • 1 <= k <= n
  • 1 <= queries.length <= 105
  • queries[i] == [li, ri]
  • 0 <= li < ri <= n - 1

Solutions

Solution 1

1


1


1


1

Comments