Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Interesting Subarray

Limits: 1s, 512 MB

You will be given an array A of length N and two more integers K and X. You have to find the length of the largest interesting sub-array inside the array A.

A sub-array is called interesting if the following two conditions are satisfied.

  • The largest element in that sub-array is K.
  • The number of occurrences of K in that sub-array is at least X.

Find the maximum length of a sub-array which is called interesting.


The first line of the input contains a single integer T which denotes the number of test cases. The first line of a test case contains three integers N, K and X. The next line of the test case contains N space separated integers denoting the elements of the array A.


${1 \leq T \leq 10}$
${1 \leq N \leq 50000}$
${1 \leq X \leq N}$
${1 \leq A_{i}, K \leq 1000000}$


For each of the test cases, print the result in a single line. If there’s no valid interesting sub-array then print -1.


8 6 2
6 2 6 3 8 2 1 6
12 6 2
6 2 6 8 2 1 6 6 4 6 9 3

In the first test case of the sample I/O, the largest interesting sub-array starts at index 1 and ends at index 4 (1 based indexing). In this sub-array, 6 occurs 2 times (which is >= X) and 6 is the largest element, so it’s an interesting sub-array. No other interesting sub-array has length greater than 4.


Login to submit