LeetCode 1664 - Ways to Make a Fair Array

The problem gives us an integer array nums, and asks us to remove exactly one element from the array. After removing that element, the remaining elements shift left, which means their indices may change.

leetcodemediumarrayprefix-sum

LeetCode Problem 1664

Difficulty: 🟡 Medium
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem gives us an integer array nums, and asks us to remove exactly one element from the array. After removing that element, the remaining elements shift left, which means their indices may change.

An array is considered fair if:

  • The sum of elements at even indices equals the sum of elements at odd indices.

Our task is to count how many indices can be removed such that the resulting array becomes fair.

The important detail is that removing one element changes the parity of all elements that come after it. Elements before the removed index keep their original positions, but every element after the removed index shifts left by one position. That means:

  • An element originally at an even index may become odd.
  • An element originally at an odd index may become even.

This parity flip is the core challenge of the problem.

For example, consider:

nums = [2,1,6,4]

If we remove index 1, the resulting array becomes:

[2,6,4]

Now the indices are:

index: 0 1 2
value: 2 6 4

The even-index sum is:

2 + 4 = 6

The odd-index sum is:

6

They are equal, so removing index 1 works.

The constraints are important:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4

An O(n^2) solution will be too slow for arrays of size 100000. We need a linear or near-linear solution.

Several edge cases are important:

  • Arrays with only one element.
  • Arrays where every removal works.
  • Arrays where no removal works.
  • Cases where parity changes dramatically after removal.
  • Arrays with alternating large and small values.

A naive implementation can easily make mistakes by forgetting that indices after the removed element shift parity.

Approaches

Brute Force Approach

The most direct solution is to try removing every index one by one.

For each index:

  1. Create a new array without that element.
  2. Compute the sum of even-indexed elements.
  3. Compute the sum of odd-indexed elements.
  4. Check whether they are equal.

This approach is correct because it explicitly simulates every possible removal and directly checks the fairness condition.

However, it is inefficient.

If the array has n elements:

  • We try n removals.
  • Each removal requires scanning up to n elements.

This leads to O(n^2) time complexity.

With n = 100000, this becomes far too slow.

Optimal Prefix Sum Approach

The key observation is that after removing an element:

  • Elements before the removed index keep the same parity.
  • Elements after the removed index switch parity.

Instead of rebuilding arrays repeatedly, we can precompute:

  • Total sum of even-indexed elements.
  • Total sum of odd-indexed elements.

Then, while iterating through the array, we maintain:

  • Prefix even sum.
  • Prefix odd sum.

For a removal at index i, we can calculate:

  • New even-index sum after removal.
  • New odd-index sum after removal.

in constant time.

This reduces the total complexity to O(n).

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Simulates every removal and rebuilds arrays
Optimal O(n) O(1) Uses running prefix sums and parity switching

Algorithm Walkthrough

Step 1: Compute Total Even and Odd Sums

First, scan the array once and compute:

  • total_even, sum of elements at even indices
  • total_odd, sum of elements at odd indices

These represent the original array before any removal.

Step 2: Maintain Prefix Sums

As we iterate through the array, we maintain:

  • left_even, sum of even-indexed elements before the current index
  • left_odd, sum of odd-indexed elements before the current index

Initially, both are zero because no elements are on the left side yet.

Step 3: Simulate Removing Each Index

Suppose we remove index i.

The array splits into two parts:

  • Left side, elements before i
  • Right side, elements after i

The left side keeps the same parity.

The right side changes parity because all elements shift left by one position.

Step 4: Calculate New Even Sum

The new even-index sum consists of:

  1. Original even-indexed elements on the left
  2. Original odd-indexed elements on the right, because they shift parity

If nums[i] is even-indexed:

right_odd = total_odd - left_odd

If nums[i] is odd-indexed:

right_odd = total_odd - left_odd - nums[i]

A cleaner unified approach is:

new_even = left_even + (total_odd - left_odd - removed_if_odd)

But we can simplify using direct formulas during iteration.

Step 5: Calculate New Odd Sum

Similarly, the new odd-index sum consists of:

  1. Original odd-indexed elements on the left
  2. Original even-indexed elements on the right

because the right side flips parity.

Step 6: Compare the Two Sums

If:

new_even == new_odd

then removing index i makes the array fair.

Increment the answer.

Step 7: Update Prefix Sums

After processing index i, add nums[i] to either:

  • left_even, if i is even
  • left_odd, if i is odd

Then continue.

Why it works

The algorithm works because it correctly models how indices change after removal.

For every removal:

  • Elements before the removed index retain parity.
  • Elements after the removed index flip parity.

By separating the array into left and right sections and using prefix sums, we can reconstruct the resulting even and odd sums in constant time for every index.

Since every index is checked exactly once and the parity transitions are handled correctly, the algorithm always produces the correct answer.

Python Solution

from typing import List

class Solution:
    def waysToMakeFair(self, nums: List[int]) -> int:
        total_even = 0
        total_odd = 0

        for i, value in enumerate(nums):
            if i % 2 == 0:
                total_even += value
            else:
                total_odd += value

        left_even = 0
        left_odd = 0
        result = 0

        for i, value in enumerate(nums):
            if i % 2 == 0:
                right_even = total_even - left_even - value
                right_odd = total_odd - left_odd
            else:
                right_even = total_even - left_even
                right_odd = total_odd - left_odd - value

            new_even = left_even + right_odd
            new_odd = left_odd + right_even

            if new_even == new_odd:
                result += 1

            if i % 2 == 0:
                left_even += value
            else:
                left_odd += value

        return result

The implementation starts by computing the total sums for even and odd indices. These totals represent the entire array before any removal.

Next, the algorithm iterates through the array while maintaining prefix sums for the left side.

For every index:

  • The current value is temporarily removed.
  • The remaining right-side sums are computed.
  • The right side switches parity after removal.
  • The new even and odd sums are reconstructed.

If the reconstructed sums are equal, the index contributes to the answer.

Finally, the current element is added into the appropriate left-side prefix sum so future iterations treat it as part of the left section.

The implementation uses only constant extra space and processes each element exactly once.

Go Solution

func waysToMakeFair(nums []int) int {
	totalEven := 0
	totalOdd := 0

	for i, value := range nums {
		if i%2 == 0 {
			totalEven += value
		} else {
			totalOdd += value
		}
	}

	leftEven := 0
	leftOdd := 0
	result := 0

	for i, value := range nums {
		var rightEven int
		var rightOdd int

		if i%2 == 0 {
			rightEven = totalEven - leftEven - value
			rightOdd = totalOdd - leftOdd
		} else {
			rightEven = totalEven - leftEven
			rightOdd = totalOdd - leftOdd - value
		}

		newEven := leftEven + rightOdd
		newOdd := leftOdd + rightEven

		if newEven == newOdd {
			result++
		}

		if i%2 == 0 {
			leftEven += value
		} else {
			leftOdd += value
		}
	}

	return result
}

The Go implementation follows the same logic as the Python version.

Go uses explicit integer variables instead of Python's dynamic integers. Integer overflow is not a concern here because the maximum possible sum is:

10^5 * 10^4 = 10^9

which safely fits inside Go's standard int type on LeetCode platforms.

Slices are used directly, and no additional arrays are allocated, keeping the space complexity at O(1).

Worked Examples

Example 1

nums = [2,1,6,4]

Initial totals:

Index Value Parity Running Total
0 2 Even total_even = 2
1 1 Odd total_odd = 1
2 6 Even total_even = 8
3 4 Odd total_odd = 5

Final totals:

total_even = 8
total_odd = 5

Now iterate through removals.

i value left_even left_odd right_even right_odd new_even new_odd Fair?
0 2 0 0 6 5 5 6 No
1 1 2 0 6 4 6 6 Yes
2 6 2 1 0 4 6 1 No
3 4 8 1 0 0 8 1 No

Answer:

1

Example 2

nums = [1,1,1]

Initial totals:

total_even = 2
total_odd = 1
i value new_even new_odd Fair?
0 1 1 1 Yes
1 1 1 1 Yes
2 1 1 1 Yes

Answer:

3

Example 3

nums = [1,2,3]

Initial totals:

total_even = 4
total_odd = 2
i value new_even new_odd Fair?
0 1 2 3 No
1 2 1 3 No
2 3 1 2 No

Answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) One pass for totals and one pass for evaluation
Space O(1) Only a few integer variables are used

The algorithm processes the array twice:

  1. First pass computes total even and odd sums.
  2. Second pass evaluates every possible removal.

Each operation inside the loop is constant time, so the total runtime is linear.

No auxiliary arrays or hash maps are needed, so the extra space usage remains constant.

Test Cases

from typing import List

class Solution:
    def waysToMakeFair(self, nums: List[int]) -> int:
        total_even = 0
        total_odd = 0

        for i, value in enumerate(nums):
            if i % 2 == 0:
                total_even += value
            else:
                total_odd += value

        left_even = 0
        left_odd = 0
        result = 0

        for i, value in enumerate(nums):
            if i % 2 == 0:
                right_even = total_even - left_even - value
                right_odd = total_odd - left_odd
            else:
                right_even = total_even - left_even
                right_odd = total_odd - left_odd - value

            new_even = left_even + right_odd
            new_odd = left_odd + right_even

            if new_even == new_odd:
                result += 1

            if i % 2 == 0:
                left_even += value
            else:
                left_odd += value

        return result

solution = Solution()

assert solution.waysToMakeFair([2, 1, 6, 4]) == 1  # provided example
assert solution.waysToMakeFair([1, 1, 1]) == 3  # every removal works
assert solution.waysToMakeFair([1, 2, 3]) == 0  # no valid removal
assert solution.waysToMakeFair([5]) == 1  # single element becomes empty array
assert solution.waysToMakeFair([1, 2]) == 0  # small array with no solution
assert solution.waysToMakeFair([2, 1]) == 0  # parity changes but still unfair
assert solution.waysToMakeFair([1, 1]) == 2  # both removals work
assert solution.waysToMakeFair([10, 10, 10, 10]) == 0  # symmetric but unfair after removal
assert solution.waysToMakeFair([0, 0, 0, 0]) == 4  # all zeros
assert solution.waysToMakeFair([10000] * 1000) == 0  # large repeated values
Test Why
[2,1,6,4] Validates the main example
[1,1,1] Ensures every index can work
[1,2,3] Ensures zero valid removals are handled
[5] Tests minimum array size
[1,2] Small non-working case
[2,1] Checks parity handling in tiny arrays
[1,1] Small array where all removals work
[10,10,10,10] Verifies symmetry does not guarantee fairness
[0,0,0,0] Tests repeated neutral values
[10000] * 1000 Stress test with large repeated numbers

Edge Cases

Single Element Array

If the array contains only one element, removing it leaves an empty array.

An empty array has:

even sum = 0
odd sum = 0

which is fair.

This case can easily be overlooked if the implementation assumes at least one remaining element. The current solution handles it naturally because both reconstructed sums become zero.

Parity Switching After Removal

The most error-prone aspect of the problem is that elements after the removed index change parity.

For example:

[2,1,6,4]

Removing 1 produces:

[2,6,4]

The original even-indexed 6 becomes odd-indexed after shifting.

A buggy implementation may incorrectly keep original parity assignments. The prefix sum method explicitly models the left side and right side separately, ensuring parity switching is handled correctly.

Arrays Where Every Removal Works

Arrays such as:

[1,1,1]

can produce a fair array regardless of which index is removed.

Some implementations accidentally stop after finding the first valid index or incorrectly reuse state between iterations. This solution independently evaluates every removal and correctly counts all valid indices.

Large Inputs

The constraint allows arrays of size 100000.

A brute-force solution that rebuilds arrays repeatedly will time out. The prefix-sum solution avoids repeated work and guarantees linear performance, making it efficient even at maximum input size.