Bob's Quest | Practice Problems

Bob's Quest

★★★★★

3.7

7 votes

C++, Greedy Algorithms, Algorithms, Observation, Sliding Window, Basics of Greedy Algorithms

Details

Problem

Bob has an array $A$ of size $N$ , and he is very fond of two integers $X$ and $Y$ . Find the length of the longest subarray, such that it contains exactly $X$ distinct integers and $Y$ exist at least once in the subarray.

Input format

The first line contains an integer $T$ , which denotes the number of test cases.
The first line of each test case contains three space separated integers $N$ , $X$ , $Y$ denoting the size of array $A$ , the value of $X$ and $Y$ , respectively.
The second line of each test case contains $N$ space-separated integers, denoting the elements of array $A$ .

Output format

For each test case, print the length of the largest subarray, such that it contains exactly $X$ distinct integers and $Y$ exist at least once in the subarray in a new line.

Constraints

$1 \leq T \leq 10 \\ 1 \leq N \leq 10^5 \\ 0 \leq A[i] \leq 10^5 \\ 1 \leq X, Y \leq 10^5$

Sample Input

Sample Output

2
0

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For test case $1$ : There exists only one subarray having exactly 2 distinct elements and having at least one occurrence of $1$ , i.e. $[3,1]$ of length $2$ . Therefore, the answer will be $2$ .

For test case $2$ : $2$ is not present in the whole array $A$ . So, the answer is $0$ .

Contributers:

Rohit Pradhan

Madhumeeta Bauk