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.
This approach utilizes prefix sums to efficiently determine the fairness of the array after removing each element. The strategy involves computing cumulative sums for elements at even and odd indices separately. For each potential removal at index i, update the prefix sums and check if the remaining even and odd indexed elements have equal sums.
The function waysToMakeFair computes prefix sums separately for elements at even and odd indices. It maintains two arrays, prefix_even and prefix_odd, which accumulate sums at even and odd indices, respectively.
For each element at index i (considered removal point), adjust the sums by excluding the influence of nums[i] on the subsequent total. Verify if the adjusted odd and even sums remain equal. If they do, increment the count.
Time Complexity: O(n), where n is the length of the nums array, because it processes each element a constant number of times.
Space Complexity: O(n) for storing prefix sums.
In this approach, we make use of a sliding window mechanism to maintain the running sums of separated even and odd indexed elements. This allows us to not use separate prefix arrays, but rather dynamically update the ongoing sums as we consider each element's removal.
This JavaScript implementation uses two sums (evenSum and oddSum) to track which indices should be affected by the future removal of elements. As each index i is considered, one can calculate the parity-sensitive potential impact of its removal on the fairness of the remaining array while updating the running counters.
JavaScript
C
Time Complexity: O(n), where n is length of nums, being simple passes through the array.
Space Complexity: O(1), as no additional space proportional to n is used.
First, we preprocess to get the sum s_1 of the elements at even indices and the sum s_2 of the elements at odd indices in the array nums.
Then, we enumerate each element v in the array nums from front to back, using variables t_1 and t_2 to record the sum of the elements at even indices and the sum of the elements at odd indices that have been traversed, respectively.
We observe that for the current element v being traversed, if it is removed, the sum of the elements at odd and even indices after this element will be swapped. At this point, we first determine whether the index i of the current position is odd or even.
If it is an even index, after deleting the element, the sum of the elements at odd indices in the array is t_2 + s_1 - t_1 - v, and the sum of the elements at even indices is t_1 + s_2 - t_2. If these two sums are equal, it is a balanced array, and the answer is incremented by one.
If it is an odd index, after deleting the element, the sum of the elements at even indices in the array is t_1 + s_2 - t_2 - v, and the sum of the elements at odd indices is t_2 + s_1 - t_1. If these two sums are equal, it is a balanced array, and the answer is incremented by one.
Then we update t_1 and t_2 and continue to traverse the next element. After traversing the array, we can get the answer.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Prefix Sums Approach | Time Complexity: Space Complexity: |
| Sliding Window Approach | Time Complexity: Space Complexity: |
| Enumeration + Prefix Sum | — |
| 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 |
Ways to Make a Fair Array || Leetcode • Pepcoding • 5,119 views views
Watch 9 more video solutions →Practice Ways to Make a Fair Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor