1664. Ways to Make a Fair Array

Array
Prefix Sum

TIME

O(n)

SPACE

O(1)

Intuition

Removing index i shifts every element after i one position left, which flips its parity (even index ↔ odd index). Elements before i keep their parity. So the fairness of the resulting array depends only on four running sums: even/odd sums of the prefix (before i) and even/odd sums of the suffix (after i), with the suffix contributions swapped because of the parity flip.

Approach

Compute total even-index sum and odd-index sum of the whole array.
Sweep i from left to right, maintaining preEven, preOdd = even/odd sums strictly before i.
The suffix sums after i are sufEven = totalEven - preEven - (nums[i] if i even) and likewise for odd, i.e. remove the prefix and nums[i] itself from the totals.
After removal, the new sums are:
- newEven = preEven + sufOdd (suffix parity flips)
- newOdd = preOdd + sufEven Count i where newEven == newOdd.
Update the running prefix with nums[i] before moving on.

Complexity

Time: O(n)
Space: O(1)

Edge Cases

Single element → removing it leaves an empty (fair) array → count 1
All equal values (Example 2) → every removal is fair
Sums up to ~10^9 fit in 32-bit, but long in Java is safe
nums[i] itself must be excluded from both prefix and suffix at index i

Code

from typing import List


class Solution:
    def waysToMakeFair(self, nums: List[int]) -> int:
        """
        1664. Ways to Make a Fair Array
        Time: O(n)
        Space: O(1)
        """
        n = len(nums)
        total_even = sum(nums[i] for i in range(0, n, 2))
        total_odd = sum(nums[i] for i in range(1, n, 2))

        pre_even = pre_odd = 0
        count = 0
        for i, x in enumerate(nums):
            # suffix sums (after i), excluding nums[i] itself
            if i % 2 == 0:
                suf_even = total_even - pre_even - x
                suf_odd = total_odd - pre_odd
            else:
                suf_even = total_even - pre_even
                suf_odd = total_odd - pre_odd - x
            # removal flips suffix parity
            if pre_even + suf_odd == pre_odd + suf_even:
                count += 1
            # advance prefix with nums[i]
            if i % 2 == 0:
                pre_even += x
            else:
                pre_odd += x
        return count

/**
 * 1664. Ways to Make a Fair Array
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public int waysToMakeFair(int[] nums) {
        int n = nums.length;
        long totalEven = 0, totalOdd = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                totalEven += nums[i];
            } else {
                totalOdd += nums[i];
            }
        }

        long preEven = 0, preOdd = 0;
        int count = 0;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            long sufEven, sufOdd;
            if (i % 2 == 0) {
                sufEven = totalEven - preEven - x;
                sufOdd = totalOdd - preOdd;
            } else {
                sufEven = totalEven - preEven;
                sufOdd = totalOdd - preOdd - x;
            }
            // removal flips suffix parity
            if (preEven + sufOdd == preOdd + sufEven) {
                count++;
            }
            if (i % 2 == 0) {
                preEven += x;
            } else {
                preOdd += x;
            }
        }
        return count;
    }
}