jhjfbsbfkbjfnfnfjfj's blog

Small Doubt
By jhjfbsbfkbjfnfnfjfj, history, 5 years ago, In English

Hello everyone, can you please help me in this problem? If I am given an array of n integers of k distinct elements. Then how do I compute the maximum subarray which has exactly f distinct elements (f< k). (like of all the subarray which has f distinct elements among them the maximum length ) Example question: (in this problem f==k-1) https://www.codechef.com/problems/NOTALLFL

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

Let us assume we have a way of finding the number of distinct elements in interval $$$[a,b]$$$.

We will iterate over every possible endpoint of the subarray from $$$1$$$ to $$$n$$$ and run a binary search for the largest size of the subarray with $$$f$$$ distinct elements. Print the maximum over all. It works because the number of distinct elements can only increase with size.

Now, about finding number of distinct elements in $$$[a,b]$$$. That can be done if we construct a segment tree with vector/set in each node. I assume it is not too hard to figure out how merge and query will work here.

The time complexity is $$$O(nlog^2n)$$$ (presumably).

Please point out the flaws in my solution if any.

Edit: I kinda don't have confidence in the part about distinct elements in subarray, this link is better.

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

You can use a sliding window. Use an array (or a map if the numbers can be big) to count how many times number $$$x$$$ is in your current range. At first $$$l$$$=$$$r$$$=$$$0$$$. Each time move $$$r$$$ forward by one and while you have more than $$$f$$$ distinct elements move $$$l$$$ forward. When you move $$$l$$$ and $$$r$$$ update your count array. If the count of numbers $$$x$$$ become 0 decrease the number of distinct elements by 1, if it was 0 and become 1 increase the number of distinct elements. If the number of distinct elements is exactly $$$f$$$ update the answer. Complexity $$$O$$$($$$N$$$)

→ Reply