Teaching Kids Programming – Set Split Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of positive integers nums, return whether you can divide the list into two groups a and b such that:

The sum of a and the sum of b are equal.
Every number in a is strictly less than every number in b.

Constraints
1 ≤ n ≤ 100,000 where n is the length of nums.
Example 1
Input
nums = [4, 9, 5]
Output
True
Explanation
We can have a = [4, 5] and b = [9] and both of their sums are 9.

Example 2
Input
nums = [9, 9]
Output
False
Explanation
We can have a = [9] and b = [9] but it doesn’t meet this criteria: “Every number in a is strictly less than every number in b.”

We can bruteforce but that takes O(2^n) to exhaust group search and then, we need to check if the numbers in one group are strictly smaller than another. Finally we need to compute the sum and compare if sum is equal for two groups. The over time complexity is exponential.

Greedy by Sorting – Split Set into Two Groups

A better algorithm would be to sort and apply the greedy algorithm. If we sort, we can pick numbers from smallest to largest. And we have running sum to see if it becomes half. We also need to check if the current number is strictly smaller than next number (could be the same).

If the size of the array is less than 3, we can’t split the set into two groups with equal sum and also satisfy that numbers in one group are strictly smaller than another. Also, if the sum of entire array is an odd number – it is also impossible to do so.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def setSplit(self, nums):
        if len(nums) < 3: 
            return False
        nums.sort()
        s = sum(nums)
        if s & 1:
            return False
        c = 0
        for i in range(len(nums) - 1):
            c += nums[i]
            if c * 2 == s and nums[i] < nums[i + 1]:
                return True
            if c * 2 > s:
                return False
        return False

class Solution:
    def setSplit(self, nums):
        if len(nums) < 3: 
            return False
        nums.sort()
        s = sum(nums)
        if s & 1:
            return False
        c = 0
        for i in range(len(nums) - 1):
            c += nums[i]
            if c * 2 == s and nums[i] < nums[i + 1]:
                return True
            if c * 2 > s:
                return False
        return False

As we need to sort the numbers first, the time complexity is O(NLogN) and going through the numbers to calculate the running sum takes O(N) time which is trivial. The space complexity is O(1) as we are not using any additional space.

See also: Split a Set into Two with Equal Sums and Distinct Numbers

–EOF (The Ultimate Computing & Technology Blog) —