Problem statement

https://binarysearch.com/problems/Every-Sublist-Containing-Unique-Element/

Solution 1

The idea of this problem is to try to find element with unique occurunce: if we found it, we can split problem into two subproblems. If not, we can return False. Now the question is how to look for this element. One way is to start for look from the middle.

Complexity

It is O(n^2) in the worst case, but O(n log n) in average. However I think there will be test to broke it.

Code

class Solution:
    def solve(self, nums):
        if not nums: return True
        n, cnt = len(nums), Counter(nums)
        rang = sorted(range(n), key = lambda x: abs(x-n//2))
        for i in rang:
            if cnt[nums[i]] == 1:
                return self.solve(nums[:i]) and self.solve(nums[i+1:])
        return False

Solution 2

There is better solution. First let us precalculate for every index the closest left and right elements with the same value. Then we use function unique(beg, end), where we start to traverse from both ends of range and look for unique elements.

Complexity

Reccurent formula for time complexity will be $F(n) = F(k) + F(n - k) + O(\min(k, n - k))$, which can be solved as $O(n log n)$, because each element will be looked at no more than log n times. Space is O(n).

Code

class Solution:
    def solve(self, A):
        def find_next(A, dr, x):
            ans, last = [x] * n, {}
            for i, v in list(enumerate(A))[::dr]:
                if v in last: ans[i] = last[v]
                last[v] = i
            return ans

        def unique(beg, end):
            if beg > end: return True
            b, e = beg, end
            for i in range(end - beg + 1):
                val = beg if i % 2 == 0 else end
                if i % 2 == 0:
                    beg += 1
                else:
                    end -= 1
                if nxt_idx[val] > e and prv_idx[val] < b:
                    return unique(b, val - 1) and unique(val + 1, e)
            return False

        n = len(A)
        prv_idx = find_next(A, 1, -1)
        nxt_idx = find_next(A, -1, n)
        return unique(0, n-1)