Watch 10 video solutions for Ways to Make a Fair Array, a medium level problem involving Array, Prefix Sum. This walkthrough by Pepcoding has 5,119 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums. You can choose exactly one index (0-indexed) and remove the element. Notice that the index of the elements may change after the removal.
For example, if nums = [6,1,7,4,1]:
1 results in nums = [6,7,4,1].2 results in nums = [6,1,4,1].4 results in nums = [6,1,7,4].An array is fair if the sum of the odd-indexed values equals the sum of the even-indexed values.
Return the number of indices that you could choose such that after the removal, nums is fair.
Example 1:
Input: nums = [2,1,6,4] Output: 1 Explanation: 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 Explanation: You can remove any index and the remaining array is fair.
Example 3:
Input: nums = [1,2,3] Output: 0 Explanation: You cannot make a fair array after removing any index.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 104Problem Overview: You are given an integer array. After removing exactly one element, the array becomes fair if the sum of elements at even indices equals the sum of elements at odd indices. The task is to count how many indices you can remove to make this condition true.
Approach 1: Prefix Sums (O(n) time, O(n) space)
The key challenge is that removing an element shifts the parity of all elements to its right. Elements that were at even indices may become odd, and vice versa. Using prefix sum, you precompute cumulative sums of values at even and odd indices separately. For each index i, calculate the even and odd sums on the left using prefix arrays, and compute the right side by subtracting from the totals. Because the parity flips after removal, right-side even contributions become odd and vice versa. If the resulting even and odd sums match, the index is valid. This approach scans the array once after preprocessing, giving O(n) time and O(n) extra space.
Approach 2: Sliding Window / Running Sums (O(n) time, O(1) space)
You can avoid storing full prefix arrays by maintaining running sums while iterating. First compute total sums of even and odd indices. As you iterate through the array, treat the current index as the removed element. Maintain leftEven and leftOdd for elements already processed. The remaining elements form the right side, whose parity flips after removal. Compute the new even sum as leftEven + (rightOdd) and the new odd sum as leftOdd + (rightEven). Update running sums as the window moves forward. This technique resembles a sliding window over prefix state and achieves the optimal O(n) time with O(1) extra space.
Recommended for interviews: Interviewers typically expect the prefix-sum reasoning. It demonstrates that you recognize how index parity changes after removal. Showing the prefix-sum solution proves correctness quickly, while the constant-space running-sum version shows deeper optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sums | O(n) | O(n) | Best for clarity during interviews and when prefix arrays make reasoning about parity shifts easier |
| Sliding Window / Running Sums | O(n) | O(1) | Preferred when optimizing memory or writing a concise single-pass solution |