Problem Description

You are given an integer array nums. You need to find how many indices you can choose to remove such that after removing exactly one element at that index, the resulting array becomes "fair".

An array is considered fair when the sum of all elements at even indices (0, 2, 4, ...) equals the sum of all elements at odd indices (1, 3, 5, ...).

The key insight is that when you remove an element at index i, all elements after position i shift left by one position, which means:

• Elements that were at even indices after i will now be at odd indices
• Elements that were at odd indices after i will now be at even indices

For example, given nums = [6,1,7,4,1]:

• Original even indices sum: 6 + 7 + 1 = 14 (indices 0, 2, 4)
• Original odd indices sum: 1 + 4 = 5 (indices 1, 3)
• If we remove index 1 (value 1), we get [6,7,4,1]:
  • New even indices sum: 6 + 4 = 10 (indices 0, 2)
  • New odd indices sum: 7 + 1 = 8 (indices 1, 3)
  • This is not fair since 10 ≠ 8

The solution tracks:

• s1: Total sum of elements at even indices in the original array
• s2: Total sum of elements at odd indices in the original array
• t1: Running sum of elements at even indices up to current position
• t2: Running sum of elements at odd indices up to current position

For each position i, it calculates what the even and odd sums would be after removing element at index i, accounting for the index shifts that occur after removal. The answer counts how many positions result in equal even and odd sums after removal.

Intuition

The critical observation is understanding what happens when we remove an element at index i: all elements after position i experience an index shift. Elements that were at even positions become odd-positioned, and vice versa.

Let's think about how to calculate the sums after removing an element at index i:

1. Elements before index i: These keep their original positions (even stays even, odd stays odd)
2. Element at index i: This gets removed
3. Elements after index i: These all shift left by one position, flipping their parity (even becomes odd, odd becomes even)

If we denote:

• t1 = sum of even-indexed elements from start up to (but not including) index i
• t2 = sum of odd-indexed elements from start up to (but not including) index i
• s1 = total sum of all even-indexed elements in original array
• s2 = total sum of all odd-indexed elements in original array

Then after removing element at index i:

• If i is even:

  • New even sum = t1 (before i) + s2 - t2 (odd elements after i that become even)
  • New odd sum = t2 (before i) + s1 - t1 - nums[i] (even elements after i that become odd, excluding nums[i])

• If i is odd:

  • New even sum = t1 (before i) + s2 - t2 - nums[i] (odd elements after i that become even, excluding nums[i])
  • New odd sum = t2 (before i) + s1 - t1 (even elements after i that become odd)

This approach allows us to check each position in a single pass through the array. We maintain running sums (t1, t2) as we traverse, and for each position, we can calculate in O(1) time whether removing that element would create a fair array. This gives us an efficient O(n) solution instead of the naive O(n²) approach of actually removing each element and recalculating sums.

Learn more about Prefix Sum patterns.

Solution Approach

The implementation follows a single-pass algorithm with prefix sum tracking:

Step 1: Calculate Initial Sums

s1, s2 = sum(nums[::2]), sum(nums[1::2])

• s1 stores the total sum of elements at even indices (0, 2, 4, ...)
• s2 stores the total sum of elements at odd indices (1, 3, 5, ...)
• Using Python slicing nums[::2] gets every other element starting from index 0, and nums[1::2] gets every other element starting from index 1

Step 2: Initialize Tracking Variables

ans = t1 = t2 = 0

• ans counts the number of valid removal positions
• t1 tracks the running sum of even-indexed elements seen so far
• t2 tracks the running sum of odd-indexed elements seen so far

Step 3: Iterate Through Each Position

for i, v in enumerate(nums):

For each element v at position i, we check if removing it would create a fair array.

Step 4: Check Fairness After Removal

For even index (i % 2 == 0):

ans += i % 2 == 0 and t2 + s1 - t1 - v == t1 + s2 - t2

• Left side t2 + s1 - t1 - v: New odd sum after removal
  • t2: odd elements before position i
  • s1 - t1 - v: even elements after position i (excluding current element v) that become odd
• Right side t1 + s2 - t2: New even sum after removal
  • t1: even elements before position i
  • s2 - t2: odd elements after position i that become even

For odd index (i % 2 == 1):

ans += i % 2 == 1 and t2 + s1 - t1 == t1 + s2 - t2 - v

• Left side t2 + s1 - t1: New odd sum after removal
  • t2: odd elements before position i
  • s1 - t1: even elements after position i that become odd
• Right side t1 + s2 - t2 - v: New even sum after removal
  • t1: even elements before position i
  • s2 - t2 - v: odd elements after position i (excluding current element v) that become even

Step 5: Update Running Sums

t1 += v if i % 2 == 0 else 0
t2 += v if i % 2 == 1 else 0

After checking the current position, we update our running sums:

• If i is even, add v to t1
• If i is odd, add v to t2

The boolean expressions in the ans += lines evaluate to 1 (True) when both conditions are met, incrementing the answer counter. This elegant approach avoids explicit if-statements while maintaining clarity.

Time Complexity: O(n) - single pass through the array Space Complexity: O(1) - only using a constant amount of extra variables

Example Walkthrough

Let's walk through the solution with nums = [2, 1, 6, 4]:

Initial Setup:

• Calculate total sums:
  • s1 (even indices sum) = nums[0] + nums[2] = 2 + 6 = 8
  • s2 (odd indices sum) = nums[1] + nums[3] = 1 + 4 = 5
• Initialize: ans = 0, t1 = 0, t2 = 0

Iteration 1 (i=0, v=2):

• Check if removing index 0 creates a fair array
• Since i=0 is even:
  • New odd sum = t2 + (s1 - t1 - v) = 0 + (8 - 0 - 2) = 6
  • New even sum = t1 + (s2 - t2) = 0 + (5 - 0) = 5
  • Is 6 == 5? No, so don't increment ans
• Update: t1 = 0 + 2 = 2 (add to even sum since i is even)

Iteration 2 (i=1, v=1):

• Check if removing index 1 creates a fair array
• Since i=1 is odd:
  • New odd sum = t2 + (s1 - t1) = 0 + (8 - 2) = 6
  • New even sum = t1 + (s2 - t2 - v) = 2 + (5 - 0 - 1) = 6
  • Is 6 == 6? Yes! Increment ans = 1
• Update: t2 = 0 + 1 = 1 (add to odd sum since i is odd)

Iteration 3 (i=2, v=6):

• Check if removing index 2 creates a fair array
• Since i=2 is even:
  • New odd sum = t2 + (s1 - t1 - v) = 1 + (8 - 2 - 6) = 1
  • New even sum = t1 + (s2 - t2) = 2 + (5 - 1) = 6
  • Is 1 == 6? No, so don't increment ans
• Update: t1 = 2 + 6 = 8 (add to even sum since i is even)

Iteration 4 (i=3, v=4):

• Check if removing index 3 creates a fair array
• Since i=3 is odd:
  • New odd sum = t2 + (s1 - t1) = 1 + (8 - 8) = 1
  • New even sum = t1 + (s2 - t2 - v) = 8 + (5 - 1 - 4) = 8
  • Is 1 == 8? No, so don't increment ans
• Update: t2 = 1 + 4 = 5 (add to odd sum since i is odd)

Result: ans = 1

We found that removing the element at index 1 creates a fair array [2, 6, 4] where:

• Even indices sum: 2 + 4 = 6 (indices 0, 2)
• Odd indices sum: 6 (index 1)
• Both sums equal 6, confirming the array is fair!

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because:

• Computing s1 = sum(nums[::2]) takes O(n) time as it iterates through approximately n/2 elements
• Computing s2 = sum(nums[1::2]) takes O(n) time as it iterates through approximately n/2 elements
• The main for loop iterates through all n elements exactly once, performing constant time operations in each iteration
• Overall: O(n) + O(n) + O(n) = O(n)

The space complexity is O(1). The algorithm only uses a fixed number of variables:

• s1 and s2 store the initial sums of even and odd indexed elements
• ans, t1, and t2 are counters/accumulators
• i and v are loop variables
• No additional data structures are created that scale with input size

All variables use constant space regardless of the input array size, resulting in O(1) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Handling Index Shifts After Removal

The most common mistake is failing to recognize that when an element is removed, all elements after it shift left by one position, causing their index parity to flip.

Incorrect Approach:

# WRONG: Simply removing element and checking sums without accounting for shifts
def waysToMakeFair_wrong(nums):
    count = 0
    for i in range(len(nums)):
        temp = nums[:i] + nums[i+1:]  # Remove element at index i
        even_sum = sum(temp[::2])
        odd_sum = sum(temp[1::2])
        if even_sum == odd_sum:
            count += 1
    return count

Why it's wrong: After removing an element at index i, the indices of all subsequent elements decrease by 1. Elements that were at even indices become odd-indexed, and vice versa. The naive approach above recalculates indices in the new array but doesn't account for this shift pattern correctly.

Correct Solution: Track prefix sums and understand that:

• Elements before the removed index keep their parity
• Elements after the removed index switch their parity

2. Off-by-One Errors in Prefix Sum Calculation

Another common mistake is updating the prefix sums before checking the fairness condition, leading to incorrect calculations.

Incorrect Order:

# WRONG: Updating prefix sums before checking
for i, v in enumerate(nums):
    if i % 2 == 0:
        t1 += v  # Updated too early!
        if t2 + s1 - t1 == t1 + s2 - t2:  # Now t1 includes current element
            ans += 1
    else:
        t2 += v  # Updated too early!
        if t2 + s1 - t1 == t1 + s2 - t2:  # Now t2 includes current element
            ans += 1

Correct Order: Always check the fairness condition first, then update the prefix sums:

for i, v in enumerate(nums):
    # Check fairness BEFORE updating prefix sums
    if i % 2 == 0:
        if t2 + s1 - t1 - v == t1 + s2 - t2:
            ans += 1
        t1 += v  # Update AFTER checking
    else:
        if t2 + s1 - t1 == t1 + s2 - t2 - v:
            ans += 1
        t2 += v  # Update AFTER checking

3. Confusing Even/Odd Index Logic

It's easy to mix up the formulas for even and odd indices when calculating the new sums after removal.

Remember the pattern:

• When removing an even-indexed element: subtract its value from the even sum calculation
• When removing an odd-indexed element: subtract its value from the odd sum calculation
• The element being removed doesn't participate in either sum after removal

Visual Aid for Index i removal:

Original: [a₀, a₁, a₂, a₃, a₄, a₅, ...]
           even odd even odd even odd

Remove a₂: [a₀, a₁, a₃, a₄, a₅, ...]
            even odd even odd even  (indices after removal point shift)

Elements a₃, a₄, a₅... switch their parity!