Problem statement

https://binarysearch.com/problems/Set-Split/

Solution

Given constraints that every number in one set must be smaller than any in another, we do not have a lot of options to split data: we need to sort it and then we have no more than n options. We nedd to check that sum(nums)//2 in our accumulate sums as well as it is on the place we allowed to split, for example if we have [9, 9], we can not take it.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums):
        nums = sorted(nums)
        acc = list(accumulate(nums))
        if acc[-1] % 2 == 1: return False
        if acc[-1]//2 not in acc: return False
        idx = acc.index(acc[-1]//2)
        if nums[idx] == nums[idx + 1]: return False
        return True