Ways to Make a Fair Array: Prefix Sum Trick

You are given an integer array nums. You can remove exactly one element. After removal, the remaining elements shift to fill the gap, which changes the indices of everything after the removed element. An array is "fair" if the sum of elements at even indices equals the sum of elements at odd indices. Return the number of indices you could remove to make the array fair.

This is LeetCode 1664: Ways to Make a Fair Array, a medium problem that tests whether you can reason about how index parity flips when elements shift. The brute force approach recalculates both sums from scratch for every possible removal. The efficient approach uses prefix sums to do it in one pass.

Why this problem is tricky

The core difficulty is the index shift. When you remove an element at index i, every element after it moves one position to the left. That means elements that were at even indices become odd, and elements that were at odd indices become even. You cannot just subtract the removed element from one sum and call it done. You also have to account for all the swaps that happen to the right.

This is what separates a brute force O(n^2) solution from a clean O(n) one. If you can precompute prefix sums for even-indexed and odd-indexed elements separately, then for any removal candidate you can instantly compute what the new even and odd sums would be.

The brute force approach

def waysToMakeFair(nums):
    count = 0
    n = len(nums)
    for i in range(n):
        even_sum = 0
        odd_sum = 0
        idx = 0
        for j in range(n):
            if j == i:
                continue
            if idx % 2 == 0:
                even_sum += nums[j]
            else:
                odd_sum += nums[j]
            idx += 1
        if even_sum == odd_sum:
            count += 1
    return count

This checks every possible removal. For each one, it rebuilds the array and recomputes both sums. It works, but it is O(n^2) and will time out on large inputs.

The key insight: prefix sums with parity tracking

Here is the idea. Build prefix sums for even-indexed elements and odd-indexed elements separately. When you remove element at index i:

• Everything to the left of i keeps its original index. Even-indexed elements stay even, odd-indexed elements stay odd.
• Everything to the right of i shifts left by one. Even-indexed elements become odd, and odd-indexed elements become even.

So after removing index i, the new even-index sum is:

leftEven[i] + rightOdd[i]

And the new odd-index sum is:

leftOdd[i] + rightEven[i]

Where leftEven[i] is the sum of even-indexed elements strictly before i, rightOdd[i] is the sum of odd-indexed elements strictly after i, and so on. If these two values are equal, removing index i makes the array fair.

Walking through it step by step

Let's trace through nums = [2, 1, 6, 4]. The total even-index sum is 2 + 6 = 8 and the total odd-index sum is 1 + 4 = 5. For each removal candidate, we compute the left prefix sums and use the right remainder (with the parity swap) to check fairness.

Only removing index 1 produces a fair array. The answer is 1.

The prefix sum solution

def waysToMakeFair(nums):
    n = len(nums)
    even_sum = 0
    odd_sum = 0
    for i in range(n):
        if i % 2 == 0:
            even_sum += nums[i]
        else:
            odd_sum += nums[i]

    count = 0
    left_even = 0
    left_odd = 0
    for i in range(n):
        right_even = even_sum - left_even - (nums[i] if i % 2 == 0 else 0)
        right_odd = odd_sum - left_odd - (nums[i] if i % 2 == 1 else 0)

        new_even = left_even + right_odd
        new_odd = left_odd + right_even

        if new_even == new_odd:
            count += 1

        if i % 2 == 0:
            left_even += nums[i]
        else:
            left_odd += nums[i]

    return count

Here is what each piece does:

1. First pass: compute the total even-index sum and odd-index sum across the whole array. This takes O(n).
2. Second pass: iterate through each index as a removal candidate. At each step, you know left_even and left_odd (the prefix sums up to but not including index i).
3. Compute right_even and right_odd by subtracting the left prefix and the current element from the totals.
4. The new even sum after removal is left_even + right_odd (right side swaps parity). The new odd sum is left_odd + right_even.
5. If they are equal, increment the count.
6. After checking, add nums[i] to the appropriate left prefix sum for the next iteration.

Complexity analysis

The prefix sum solution makes two passes through the array. The first computes totals. The second checks each removal. Both are O(n). We only use a constant number of variables (no extra arrays needed), so space is O(1) beyond the input.

The building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Prefix sums for range queries

The pattern of precomputing cumulative sums so you can answer "what is the sum of this subrange?" in O(1):

prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + nums[i]
range_sum = prefix[right + 1] - prefix[left]

In this problem, you maintain separate prefix sums for even-indexed and odd-indexed elements. In Product of Array Except Self, you use prefix products. The shape is the same: accumulate a running total from the left, and derive what you need on the right by subtraction.

2. Even/odd index parity reasoning

The pattern of treating elements differently based on whether their index is even or odd:

for i in range(n):
    if i % 2 == 0:
        handle_even(nums[i])
    else:
        handle_odd(nums[i])

In this problem, index parity determines which sum an element contributes to. The twist is that removing an element flips the parity of everything after it. This same kind of parity-aware reasoning appears in problems involving alternating sequences, checkerboard patterns, and array rearrangements.

Edge cases to watch for

Before submitting, make sure your solution handles these:

• Single element nums = [1]: removing it gives an empty array with both sums equal to 0. That counts as fair. Answer is 1.
• Two elements nums = [1, 1]: removing index 0 leaves [1] (even sum = 1, odd sum = 0, not fair). Removing index 1 leaves [1] (even sum = 1, odd sum = 0, not fair). Answer is 0.
• All elements the same nums = [2, 2, 2, 2]: every removal should be checked. Symmetry might make multiple removals valid.
• All zeros nums = [0, 0, 0]: every removal gives even sum = odd sum = 0. All removals are fair.
• Large values: the sums can get large. In Python this is not an issue, but in languages with fixed-width integers, watch for overflow.
• Negative values: the prefix sum logic works the same way with negative numbers. No special handling needed.

From understanding to recall

You have read through the prefix sum approach and the parity swap makes sense. Left side keeps its indices, right side flips. Two running totals, one check per index. Clean and efficient.

But recognizing that removal causes an index parity flip is the kind of insight that slips away if you do not practice it. In an interview, the pressure makes it easy to forget the swap and just subtract the removed element from one sum. That gives wrong answers, and debugging it under a time limit is painful.

Spaced repetition fixes this. You practice writing the even/odd prefix sum split from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "removal changes indices" and immediately think "left keeps parity, right swaps." No hesitation.

The prefix sum pattern and parity reasoning are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Product of Array Except Self - Another problem where prefix/suffix sums eliminate nested loops
• Sum of Even Numbers After Queries - Tracking running sums as elements change
• Maximum Subarray - Classic prefix sum / Kadane's approach to array problems

CodeBricks breaks the ways to make a fair array LeetCode problem into its prefix sum and parity tracking building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When an index-shift question shows up in your interview, you do not think about it. You just write it.