See all coding puzzles and patterns here.
  • Difficulty: Medium

Problem Definition

Given an array of numbers, determine if it can be split into 2 subarrays A & B such that the sums of the items in the two subarrays are equal and the items in the first subarray are all less than all the items in the second subarray.

Examples

assert bal_split([2, 1, 2, 5])
assert bal_split([1, 1, 5, 7])
assert not bal_split([1, 5, 7, 1])
assert not bal_split([3, 6, 3, 4, 4])
assert not bal_split([12, 7, 6, 7, 6])

Solution

def bal_split(arr):
    mid = len(arr) // 2
    left_sum = sum(arr[:mid])
    right_sum = sum(arr[mid:])
    diff = right_sum - left_sum
    if diff > 0:
        while diff > 0 and mid > 0:
            mid += 1
            diff -= 2 * arr[mid - 1]
    elif diff < 0:
        while diff < 0 and mid < len(arr):
            mid -= 1
            diff += 2 * arr[mid]
    return diff == 0 and max(arr[:mid]) < min(arr[mid:])

Complexity

Since we have to sum both halves of the array, the best we can do in $O$ runtime is $O(n)$.

In our implementation, we are summing $\frac{n}{2} + \frac{n}{2} + \frac{n}{2} + n$ times, resulting in a runtime complexity of $O(n)$.

Auxiliary space complexity should be $O(1)$ since we are only storing a handful of constants.