-1
$\begingroup$

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

Improve this question
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$ – FrankW Sep 29 '14 at 18:17
  • 2
    $\begingroup$ 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? $\endgroup$ – FrankW Sep 29 '14 at 18:18
  • 2
    $\begingroup$ Your question is very unclear. What does subarray mean for you and what does "unique element" mean - your example doesn't help at all $\endgroup$ – d'alar'cop Sep 29 '14 at 18:30
  • $\begingroup$ 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. $\endgroup$ – Ryan Sep 29 '14 at 18:36
  • 2
    $\begingroup$ @questioner You should update your question with your clarifications. We shouldn't have to read the comments in order to understand your question. $\endgroup$ – Yuval Filmus Sep 29 '14 at 19:44
2
$\begingroup$

I'm going to assume subarray means continuous sequence. I know this problem from a programming contest.

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ – D.W.♦ Oct 6 '14 at 4:33
0
$\begingroup$

There is no need to calculate the subarray.If there is atleast one unique element in the whole array, then the array is good.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – John L. May 27 '20 at 17:59
  • $\begingroup$ There is: all subarrays contain at least one unique element, so your answer is wrong. WLOG let it be the first element that is unique and no more unique exists, then any subarray without first element fail. $\endgroup$ – Evil Oct 7 '20 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.