Ways to Make a Fair Array

The key to Ways to Make a Fair Array is that removing one element flips the parity of every index to its right. A correct solution does not rebuild the array for each choice. Instead, track even and odd sums on the left and right, then test whether left even plus right odd equals left odd plus right even after each removal.

Problem Statement

You are given an integer array nums and must remove exactly one element. After that removal, all elements to the right shift left by one position, so their indices change. Your goal is to count how many indices can be removed so that in the remaining array, the sum of values at even indices matches the sum of values at odd indices.

This index shift is the whole challenge in Ways to Make a Fair Array. When you remove position i, elements before i keep their parity, but elements after i switch from even to odd or from odd to even. For nums = [2,1,6,4], only removing index 1 works because the rebuilt array [2,6,4] has even-index sum 6 and odd-index sum 6.

Examples

Example 1

Input: nums = [2,1,6,4]

Output: 1

Remove index 0: [1,6,4] -> Even sum: 1 + 4 = 5. Odd sum: 6. Not fair. Remove index 1: [2,6,4] -> Even sum: 2 + 4 = 6. Odd sum: 6. Fair. Remove index 2: [2,1,4] -> Even sum: 2 + 4 = 6. Odd sum: 1. Not fair. Remove index 3: [2,1,6] -> Even sum: 2 + 6 = 8. Odd sum: 1. Not fair. There is 1 index that you can remove to make nums fair.

Example 2

Input: nums = [1,1,1]

Output: 3

You can remove any index and the remaining array is fair.

Example 3

Input: nums = [1,2,3]

Output: 0

You cannot make a fair array after removing any index.

Constraints

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104

Solution Approach

Brute force simulation is too slow

A direct idea is to remove each index, rebuild the remaining array, recompute even and odd sums, and count valid cases. That works logically, but it costs O(n) work per removal, leading to O(n^2) time. With nums.length up to 10^5, that approach times out even though the fairness check itself is simple.

Track parity sums on both sides

A better Array plus Prefix Sum approach separates the array into running left sums and remaining right sums. Start with totalEven and totalOdd for the full array. As you scan from left to right, treat nums[i] as the removed value. Elements left of i keep their original parity, while elements right of i flip parity after the shift. So the new even sum becomes leftEven + rightOdd, and the new odd sum becomes leftOdd + rightEven.

One pass fairness test

For each index, first subtract nums[i] from the correct right-side parity bucket. Then compare leftEven + rightOdd against leftOdd + rightEven. If they match, that removal makes the array fair. After the check, add nums[i] into the correct left-side parity bucket and continue. This gives an O(n) scan with O(1) extra space and handles the parity-flip failure mode directly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The optimal solution runs in O(n) time because each element is processed once while updating four running sums: leftEven, leftOdd, rightEven, and rightOdd. It uses O(1) extra space because you do not need a full prefix array or any rebuilt arrays; you only need parity totals and a counter. An explicit prefix-sum array version is also valid, but the compressed running-sum version is usually cleaner for this problem.

What Interviewers Usually Probe

• They mention that indices after the removed element shift, which is a direct hint that right-side parity flips.
• They ask for something faster than rebuilding the array for every index, pushing you away from O(n^2) simulation.
• They emphasize Array and Prefix Sum topics, signaling parity-based running totals instead of deletion mechanics.

Common Pitfalls or Variants

Common pitfalls

• Forgetting that only the suffix after the removed index changes parity; the prefix keeps the same even or odd positions.
• Checking original even and odd sums after subtracting nums[i] without swapping the right-side parity contribution.
• Updating left-side sums before testing the current removal, which makes nums[i] incorrectly remain in the kept array.

Follow-up variants

• Return the list of removable indices instead of the count; the same parity-sum check still works.
• Allow multiple fairness queries after point updates to nums; this pushes the problem toward segment trees or Fenwick trees with parity-aware logic.
• Ask whether removing one element can make even and odd sums differ by a target value k instead of zero; the parity-flip formula changes only in the final comparison.

FAQ

What is the main trick in Ways to Make a Fair Array?

The main trick is that removing index i changes the parity of every element to its right. That means you cannot just subtract nums[i] from the original even or odd sum; you must also swap how the suffix contributes to the final even and odd totals.

Why is prefix sum the right pattern for this problem?

This problem fits Array plus Prefix Sum because you need fast access to parity sums on both sides of each index. Prefix-style running totals let you test every removal in O(1) after O(1) updates, instead of recomputing sums for rebuilt arrays.

Can I solve Ways to Make a Fair Array with actual prefix arrays?

Yes. You can build prefixEven and prefixOdd arrays, then derive left and right parity sums for each removal. That is still O(n) time, but it uses O(n) extra space, while the running-sum version compresses the same idea into O(1) space.

Why does nums = [2,1,6,4] return 1?

Only removing index 1 works. The remaining array becomes [2,6,4], where even-index sum is 2 + 4 = 6 and odd-index sum is 6, so the array is fair. No other removal produces equal parity sums.

What update order should I use in the one-pass solution?

First remove nums[i] from the correct right-side bucket, then test fairness using leftEven + rightOdd and leftOdd + rightEven, and only after that add nums[i] to the left-side bucket. This order ensures the current index is treated as deleted instead of still present.