# Algorithm for checking if all subarrays have an unique element

How to check if all subarrays of the array contain at least one unique element for NlogN complexity, where N is the length of the array?

For example:

3 1 2 1 2 5 6 - doesn't satisfy the property (1 2 1 2 has no unique elements)

1 2 1 3 1 4 1 5 - satisfies the property

• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – FrankW Sep 29 '14 at 18:17
• What have you tried? Where did you get stuck? We want to help you with your specific problems, not just do your (home-)work. However, as it is we don't know what this problem is and thus how to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? – FrankW Sep 29 '14 at 18:18
• Your question is very unclear. What does subarray mean for you and what does "unique element" mean - your example doesn't help at all – d'alar'cop Sep 29 '14 at 18:30
• If you mean "subarrays" to mean "any subset of the elements of the array", and does not need to be proper, this would amount to checking if all elements are unique. – Ryan Sep 29 '14 at 18:36
• @questioner You should update your question with your clarifications. We shouldn't have to read the comments in order to understand your question. – Yuval Filmus Sep 29 '14 at 19:44

You can use use a divide and conquer type approach. Consider a function isGood(sequence) that answers your question. isGood() must have access to a data structure that keeps the frequency of sequence's elements in sorted order. The least frequent element must be unique, otherwise the whole sequence itself breaks your rule. Consider this element to have position SplitPoint in your array. Note that now you only have to answer your question for sequence[1...SplitPoint - 1] and sequence[SplitPoint + 1... N] independently (they should both say GOOD). This is because the element at SplitPoint guarantees that all subarrays that contain it are alright.
Ideally, SplitPoint would be in the middle of the array (this would guarantee $$N \log (N)$$). Obviously, this may not happen in general. However, notice that the bulk of your computation in isGood() involves computing the frequency table. When you split the sequence into two and recurse on the parts, you don't have to rebuild the two frequency tables again. You can split the big one into two in $$O(\text{the smaller one's size})$$. Given that the smaller part is always less than half the total size, this guarantees $$(N log(N)) * Q$$ time, where $$Q$$ is the complexity of modifying the frequency of an element (you can get $$log(N)$$ with any BST). To see why, consider the process backwards: each time you're uniting two disjoint sets in complexity $$O(\text{size of the smallest})$$. The total size of all the sets is N, therefore if you keep an eye on a particular element, it can't be in the smaller part more than $$log(N)$$ times.
• Intriguing! I'm struggling to follow why this runs in $O(N \log N)$ time, though. Can you elaborate? If at each recursive call the split was into two pieces, one with just 1 element and the other with $N-1$ elements, we'd be in trouble. Is there some explanation why that can't happen? Is there a clean recurrence relation for the running time of this algorithm? – D.W. Oct 6 '14 at 4:33
• The question says 3 1 2 1 2 5 6 is not good. Note that 5 and 6 are unique in that array. How will you explain that? – John L. May 27 '20 at 17:59