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.