Split an array into two halves with equal sums

We need an index i with sum(nums[0..i]) == sum(nums[i+1..n-1]), where both
sides are non-empty, so 0 <= i <= n - 2. Return -1 if there is none.

Brute force. For each candidate i, sum the left part and the right part
from scratch. That is O(n) work per candidate and O(n^2) overall. It is a fine
first sentence in the interview, but move on quickly.

Running prefix sum (optimal). Compute total = sum(nums) once. Walk left to
right, keeping left = nums[0] + ... + nums[i]. The right side is then
total - left, so the split is valid exactly when 2 * left == total.
One pass, O(1) extra space.

Two quick observations worth saying out loud:

• If total is odd, no split exists. Return -1 right away.
• Because every value is positive, left strictly increases. So at most one
  index can satisfy left == total / 2, and you can stop as soon as left
  passes total / 2. The answer is unique, which removes the "which index do
  we return?" ambiguity. (With zeros or negatives, several indices can work;
  see the follow-ups.)

Invariant. Before checking index i, left equals the sum of
nums[0..i], and every earlier index has been rejected. Using 2 * left == total avoids integer division and works for any integer type.

Clarify with the interviewer: both halves non-empty (so the last index is not a
valid answer), the element at the split index goes to the left side, and an
empty or single-element array returns -1.

from bisect import bisect_left
from itertools import accumulate


def find_split_index(nums: list[int]) -> int:
    """Return i such that sum(nums[:i+1]) == sum(nums[i+1:]), both non-empty.

    Assumes positive integers, so the answer is unique. Returns -1 if none.
    O(n) time, O(1) extra space.
    """
    total = sum(nums)
    if total % 2:
        return -1
    half = total // 2
    left = 0
    for i in range(len(nums) - 1):  # the right side must keep >= 1 element
        left += nums[i]
        if left == half:
            return i
        if left > half:  # positive values: left only grows from here
            return -1
    return -1


def find_split_index_brute(nums: list[int]) -> int:
    """O(n^2) baseline: recompute both sides for every candidate."""
    for i in range(len(nums) - 1):
        if sum(nums[: i + 1]) == sum(nums[i + 1 :]):
            return i
    return -1


def all_split_indices(nums: list[int]) -> list[int]:
    """Follow-up: any integers (zeros, negatives). Return every valid index."""
    total = sum(nums)
    result: list[int] = []
    left = 0
    for i in range(len(nums) - 1):
        left += nums[i]
        if 2 * left == total:
            result.append(i)
    return result


class SplitQuery:
    """Follow-up: many queries on the same positive array, each on a range.

    Precompute prefix sums once; each query is O(log n) by binary search,
    which works because prefix sums of positive values are strictly increasing.
    """

    def __init__(self, nums: list[int]) -> None:
        self.prefix = [0, *accumulate(nums)]  # prefix[k] = sum(nums[:k])

    def split(self, lo: int, hi: int) -> int:
        """Split index for nums[lo..hi] inclusive, or -1."""
        if hi - lo < 1:
            return -1
        base = self.prefix[lo]
        total = self.prefix[hi + 1] - base
        if total % 2:
            return -1
        target = base + total // 2  # need prefix[i + 1] == target
        k = bisect_left(self.prefix, target, lo + 1, hi + 1)
        if k <= hi and self.prefix[k] == target:
            return k - 1
        return -1


if __name__ == "__main__":
    cases = [
        ([4, 2, 3, 3], 1),
        ([1, 1], 0),
        ([5, 1, 2, 2], 0),
        ([1, 2, 3, 4, 10], 3),
        ([2, 3, 4], -1),
        ([1, 2, 5], -1),
        ([7], -1),
        ([], -1),
        ([3, 3, 3], -1),
    ]
    for arr, want in cases:
        assert find_split_index(arr) == want, (arr, find_split_index(arr))
        assert find_split_index_brute(arr) == want, arr
    assert all_split_indices([1, -1, 0, 0]) == [1, 2]
    assert all_split_indices([0, 0, 0]) == [0, 1]
    q = SplitQuery([9, 4, 2, 3, 3, 8])
    assert q.split(1, 4) == 2  # [4,2 | 3,3]
    assert q.split(0, 5) == -1
    assert q.split(3, 4) == 3  # [3 | 3]
    assert q.split(2, 2) == -1
    print("all tests passed")

• find_split_index: O(n) time (one pass for the total, at most one more for
  the scan), O(1) extra space.
• find_split_index_brute: O(n^2) time, O(n) space for the slices.
• all_split_indices: O(n) time, O(k) space for the k answers.
• SplitQuery: O(n) time and space to build; O(log n) per range query.

• [4, 2, 3, 3] -> 1 (4 + 2 = 3 + 3).
• [1, 1] -> 0, the smallest array that can split.
• [5, 1, 2, 2] -> 0, split right after the first element.
• [1, 2, 3, 4, 10] -> 3, split right before the last element.
• [2, 3, 4] -> -1, total is odd.
• [1, 2, 5] -> -1: total 8 is even, but the prefix jumps from 3 to 8 and
  never equals 4.
• [3, 3, 3] -> -1, total 9 is odd.
• [7] -> -1, one element cannot form two non-empty halves.
• [] -> -1.
• Large input: 10^5 values up to 10^9 -> Python ints do not overflow; in
  Java/C++ use a 64-bit accumulator.

1. Zeros or negative numbers allowed. The prefix is no longer monotonic,
   so drop the early exit (the odd-total check still holds). Several
   indices may work ([0, 0, 0] has two). Ask whether to return the first,
   the last, or all of them; all_split_indices returns all.
2. Return the most balanced split when no exact one exists. Track
   abs(total - 2 * left) and keep the index with the smallest value. With
   positive values this is a binary search on the prefix array for total / 2
   and a check of the two neighbours.
3. Many queries on subarrays [lo, hi]. Precompute prefix sums once. For
   positive values, binary search for prefix[lo] + total / 2 gives
   O(log n) per query (SplitQuery). For arbitrary integers, a hash map from
   prefix value to sorted positions answers the same question.
4. Split into k contiguous parts of equal sum. Need total % k == 0; walk
   once and cut every time the running sum reaches the next multiple of
   total / k. With positive values the cuts are forced, so it is still O(n).
   (With negatives, count prefix positions hitting each multiple in order.)
5. Non-contiguous split (any subset). This becomes Partition Equal Subset
   Sum, an NP-hard problem in general; solve with a subset-sum bitset DP in
   O(n * total / 2). Point out that this is a different problem, not a harder
   version of the same one.

Mid-level (L4)

• Clarifies non-empty halves and which side owns the split element.
• Moves from O(n^2) to the one-pass total - left check without hints.
• Handles empty, single-element and odd-total inputs; code runs first time.

Senior (L5)

• Uses positivity: notes the answer is unique and exits early once left
  passes half the total.
• Writes 2 * left == total to avoid division and mentions 64-bit sums in
  typed languages.
• Answers the zeros/negatives and "most balanced split" follow-ups cleanly.

Staff (L6+)

• Generalises to range queries with prefix sums plus binary search, and to
  k equal parts.
• Separates the contiguous problem from subset partition and explains why one
  is linear and the other needs DP.
• Drives the clarification and testing plan, and keeps the code minimal.