1664. Ways to Make a Fair Array - Detailed Explanation

Problem Statement

Description:
You are given an integer array nums. An array is called fair if the sum of the elements at even indices is equal to the sum of the elements at odd indices. Your task is to determine how many ways you can remove exactly one element from the array so that the resulting array becomes fair. Note: When you remove an element, the indices of the remaining elements change (i.e., elements to the right shift left by one).

Constraints:

• 1 ≤ nums.length ≤ 10⁵
• 1 ≤ nums[i] ≤ 10⁴

Example 1:

• Input: nums = [2, 1, 6, 4]
• Output: 1
• Explanation:
  • If you remove the element at index 1 (value 1), the array becomes [2, 6, 4].
  • New indices: 0 → 2, 1 → 6, 2 → 4
  • Even-index sum = 2 + 4 = 6, odd-index sum = 6
  • Since both sums are equal, this is a fair array.

Example 2:

• Input: nums = [1, 1, 1]
• Output: 3
• Explanation:
  • Removing any element results in a 2-element array where the first element is at index 0 and the second at index 1.
  • For every removal:
    • New array: [1, 1]
    • Even-index sum = 1, odd-index sum = 1
  • All three removal choices yield a fair array.

Example 3:

• Input: nums = [1, 2, 3]
• Output: 0
• Explanation:
  • No matter which element you remove, the sum of even-indexed elements will not equal the sum of odd-indexed ones.
  • Therefore, there are no valid removals that make the array fair.

Hints

• Hint 1: Consider how the indices change when you remove an element. The elements to the right of the removed element will shift one position to the left, changing their parity (even/odd index positions).
• Hint 2: Precompute the total sums of even and odd indexed elements. Then, as you iterate through the array, maintain cumulative sums (prefix sums) for the left side of the removal index.
• Hint 3: Use these cumulative sums to efficiently compute what the new even and odd sums would be if you remove the current element without recomputing the sum for the entire array each time.

Approaches

Brute Force Approach

Idea:
For each index in the array, remove the element and then recompute the sums for the even and odd positions for the resulting array. Count the removals that yield a fair array.

Steps:

1. Loop through every index i in nums.
2. Create a new array without nums[i].
3. Recompute the sum of elements at even indices and at odd indices.
4. Check if the two sums are equal; if so, increment a counter.

Complexity:

• Time Complexity: O(n²) in the worst case (because for each element, you scan the remaining array).
• Space Complexity: O(n) for the new array each time (if not done in place).

Visual Example:
For nums = [2, 1, 6, 4]:

• Remove index 0 → New array: [1, 6, 4] → even sum = 1 + 4 = 5, odd sum = 6
• Remove index 1 → New array: [2, 6, 4] → even sum = 2 + 4 = 6, odd sum = 6 (fair)
• Remove index 2 → New array: [2, 1, 4] → even sum = 2 + 4 = 6, odd sum = 1
• Remove index 3 → New array: [2, 1, 6] → even sum = 2 + 6 = 8, odd sum = 1

Only one removal yields a fair array.

Optimal Approach Using Prefix Sums

Idea:
Rather than simulating each removal, use prefix sums to track the cumulative sums of even-indexed and odd-indexed elements.

1. First, compute the total sum of even indices (totalEven) and odd indices (totalOdd) for the entire array.

2. Then, iterate through the array while maintaining cumulative sums for the elements to the left (leftEven, leftOdd).

3. For each index i, the right part of the array (elements after i) will shift and the parity will flip:

   • If i is even:
     • Remove nums[i] from totalEven (because it is being removed).
     • New even sum becomes: leftEven + (totalOdd - leftOdd)
     • New odd sum becomes: leftOdd + (totalEven - leftEven)
   • If i is odd:
     • Remove nums[i] from totalOdd.
     • New even sum becomes: leftEven + (totalOdd - leftOdd)
     • New odd sum becomes: leftOdd + (totalEven - leftEven)
   • Note: Although the formulas look similar, the removal step is critical (subtracting nums[i] from the respective total).

4. Check if the new even and odd sums are equal; if so, increment your counter.

5. Update the left cumulative sums with the current element (depending on its original index parity).

Complexity:

• Time Complexity: O(n) – a single pass to compute totals, then one pass to check each removal.
• Space Complexity: O(1) – using only a few extra variables.

Step-by-Step Walkthrough (Visual Example):
Consider nums = [2, 1, 6, 4]

1. Initialization:

   • totalEven = 2 + 6 = 8
   • totalOdd = 1 + 4 = 5
   • leftEven = 0, leftOdd = 0
   • Answer counter = 0

2. Iteration:

   • Index 0 (value 2, even index):
     • Remove 2 → Adjusted totalEven becomes 8 - 2 = 6
     • New even sum = leftEven (0) + (totalOdd - leftOdd = 5 - 0) = 5
     • New odd sum = leftOdd (0) + (totalEven (after removal) - leftEven = 6 - 0) = 6
     • Not fair.
     • Update leftEven = 0 + 2 = 2
   • Index 1 (value 1, odd index):
     • Remove 1 → Adjusted totalOdd becomes 5 - 1 = 4
     • New even sum = leftEven (2) + (totalOdd - leftOdd = 4 - 0) = 6
     • New odd sum = leftOdd (0) + (totalEven - leftEven = 6 - 2) = 4
     • Not fair.
     • Update leftOdd = 0 + 1 = 1
   • Index 2 (value 6, even index):
     • Remove 6 → Adjusted totalEven becomes 6 - 6 = 0
     • New even sum = leftEven (2) + (totalOdd - leftOdd = 4 - 1) = 2 + 3 = 5
     • New odd sum = leftOdd (1) + (totalEven - leftEven = 0 - 2) = 1 - 2 = -1
     • Not fair.
     • Update leftEven = 2 + 6 = 8
   • Index 3 (value 4, odd index):
     • Remove 4 → Adjusted totalOdd becomes 4 - 4 = 0
     • New even sum = leftEven (8) + (totalOdd - leftOdd = 0 - 1) = 8 - 1 = 7
     • New odd sum = leftOdd (1) + (totalEven - leftEven = 0 - 8) = 1 - 8 = -7
     • Not fair.

In this particular example, notice that a different perspective on cumulative sums may be needed. (For the sample input [2,1,6,4] the fair removal is at index 1 when computed carefully with the parity shift.)
Important: The parity flip for the right segment means the formulas are applied exactly as:

• If i is even:
  • New even = leftEven + (totalOdd - leftOdd)
  • New odd = leftOdd + (totalEven - leftEven - nums[i])
• If i is odd:
  • New even = leftEven + (totalOdd - leftOdd - nums[i])
  • New odd = leftOdd + (totalEven - leftEven)

(When following the iterative update, be sure to subtract nums[i] before computing the new sums.)
For example, re-evaluating index 1 in [2,1,6,4]:

• Index 1 (value 1, odd):
  • Before removal, totalOdd = 5. Remove nums[1] → New totalOdd becomes 5 - 1 = 4.
  • New even = leftEven (2) + (totalOdd - leftOdd) = 2 + (4 - 0) = 6
  • New odd = leftOdd (0) + (totalEven - leftEven) = 0 + (8 - 2) = 6
  • Fair removal found. (Counter becomes 1)

Code Implementation

Python Code