Given any K and an array of length $N$ what is the most efficient way to find the number of unique subarrays that satisfy this constraint? I believe there is an $O(N)$ solution using monotonic queues but am unsure of the specifics. Unique refers to the range of the original array that the subarray covers.
Asked
Active
Viewed 40 times
0
-
2The question is worded in a confusing way since it appears $A$ refers both to the array and any subarray. – Paul Jun 09 '16 at 01:22
-
You're right, I've edited it to make it more clear. – Jack Pan Jun 09 '16 at 01:25
-
What is uniqueness? [2,5,3] and [2,6,3] ,are these unique? – Mayank Deora Jun 09 '16 at 01:34
-
What's the source of this question? – joriki Jun 09 '16 at 03:16
-
@MayankDeora yes those are unique. – Jack Pan Jun 09 '16 at 18:13
-
@joriki The source of the question is https://dmoj.ca/problem/dmopc15c6p5. – Jack Pan Jun 09 '16 at 18:13
-
[1,3,5] and [1,5] ,are these unique or same? – Mayank Deora Jun 10 '16 at 02:59