Ways to Make a Fair Array
MedPrompt
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]:
- Choosing to remove index
1results innums = [6,7,4,1]. - Choosing to remove index
2results innums = [6,1,4,1]. - Choosing to remove index
4results innums = [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] <= 104
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to simulate the process directly. We can iterate through every possible index i that can be removed. For each i, we construct a new array that excludes nums[i]. Then, we iterate through this new array, calculate the sum of its even-indexed elements and odd-indexed elements, and check if they are equal. If they are, we increment a counter. This process is repeated for all possible indices.
Algorithm
- Initialize a counter
fairCountto 0. - Iterate through each index
ifrom0ton-1, wherenis the length ofnums. - For each
i, create a new temporary list or array by removing the elementnums[i]. - Initialize
evenSumandoddSumto 0. - Iterate through the temporary array. For each element at index
j:- If
jis even, add the element toevenSum. - If
jis odd, add the element tooddSum.
- If
- After iterating through the temporary array, check if
evenSumequalsoddSum. - If they are equal, increment
fairCount. - After the outer loop finishes, return
fairCount.
Walkthrough
This method involves a nested loop structure. The outer loop selects an element to remove, and the inner loop processes the resulting array.
For example, if nums = [2,1,6,4]:
- Remove index 0: New array is
[1,6,4]. Even sum (1+4)=5, Odd sum (6)=6. Not fair. - Remove index 1: New array is
[2,6,4]. Even sum (2+4)=6, Odd sum (6)=6. Fair. Increment count. - Remove index 2: New array is
[2,1,4]. Even sum (2+4)=6, Odd sum (1)=1. Not fair. - Remove index 3: New array is
[2,1,6]. Even sum (2+6)=8, Odd sum (1)=1. Not fair.
The final count is 1.
import java.util.ArrayList;import java.util.List; class Solution { public int waysToMakeFair(int[] nums) { int n = nums.length; int fairCount = 0; for (int i = 0; i < n; i++) { // Create a temporary list without the element at index i List<Integer> tempList = new ArrayList<>(); for (int j = 0; j < n; j++) { if (i != j) { tempList.add(nums[j]); } } // Calculate even and odd sums for the temporary list int evenSum = 0; int oddSum = 0; for (int j = 0; j < tempList.size(); j++) { if (j % 2 == 0) { evenSum += tempList.get(j); } else { oddSum += tempList.get(j); } } // Check if the array is fair if (evenSum == oddSum) { fairCount++; } } return fairCount; }}Complexity
Time
O(N^2), where N is the length of the input array. The outer loop runs N times. Inside the loop, creating the new list takes O(N) time, and calculating the sums also takes O(N) time. This results in a total complexity of O(N * (N + N)) = O(N^2).
Space
O(N), where N is the length of the input array. In each iteration of the outer loop, a new list of size N-1 is created.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem statement.
Cons
Highly inefficient for large input arrays, leading to a 'Time Limit Exceeded' error on most platforms.
Uses extra space proportional to the input size for each iteration.
Instead of re-calculating sums from scratch in every iteration, we can optimize the process by observing the effect of removing an element nums[i]. When nums[i] is removed, the array is split into a left part (elements before i) and a right part (elements after i). The indices in the left part remain unchanged. However, the indices of all elements in the right part decrease by one, which flips their parity (even becomes odd, odd becomes even).
We can pre-calculate the total sum of even-indexed and odd-indexed elements. Then, as we iterate through the array, we can maintain the sums of elements to the left of i (leftEvenSum, leftOddSum). With this information and the total sums, we can deduce the sums of elements to the right of i in constant time. This allows us to calculate the new sums after removal and check for fairness in O(1) for each index.
Algorithm
- First, make a single pass through the entire array to calculate the
totalEvenSumandtotalOddSum. - Initialize a counter
fairCountto 0. - Initialize
leftEvenSum = 0andleftOddSum = 0to keep track of sums of elements to the left of the current index. - Iterate through the array from index
i = 0ton-1. - In each iteration, determine the sums of the elements to the right of
i. Let's sayrightEvenSumandrightOddSum.- If
iis an even index,rightEvenSum = totalEvenSum - leftEvenSum - nums[i]andrightOddSum = totalOddSum - leftOddSum. - If
iis an odd index,rightEvenSum = totalEvenSum - leftEvenSumandrightOddSum = totalOddSum - leftOddSum - nums[i].
- If
- After removing
nums[i], the elements to its right shift their positions, flipping their index parity. The new sums will be:newEvenSum = leftEvenSum + rightOddSumnewOddSum = leftOddSum + rightEvenSum
- Check if
newEvenSum == newOddSum. If they are equal, incrementfairCount. - Before moving to the next iteration, update the
leftsums by including the current elementnums[i].- If
iis even,leftEvenSum += nums[i]. - If
iis odd,leftOddSum += nums[i].
- If
- Return
fairCount.
Walkthrough
This approach avoids creating new arrays and re-scanning. It relies on a clever calculation using prefix and suffix sums.
Let's break down the sums after removing nums[i]:
- New Even Sum: This will be the sum of elements that end up at an even index. This includes:
- Elements at even indices to the left of
i(leftEvenSum). - Elements at odd indices to the right of
i(since their indexjbecomesj-1, which is even).
- Elements at even indices to the left of
- New Odd Sum: This will be the sum of elements that end up at an odd index. This includes:
- Elements at odd indices to the left of
i(leftOddSum). - Elements at even indices to the right of
i(since their indexjbecomesj-1, which is odd).
- Elements at odd indices to the left of
By iterating once to get totals, and a second time to check each removal, we achieve a linear time solution.
class Solution { public int waysToMakeFair(int[] nums) { int n = nums.length; if (n == 0) { return 0; } // Step 1: Calculate total sums for the original array int totalEvenSum = 0; int totalOddSum = 0; for (int i = 0; i < n; i++) { if (i % 2 == 0) { totalEvenSum += nums[i]; } else { totalOddSum += nums[i]; } } int fairCount = 0; int leftEvenSum = 0; int leftOddSum = 0; // Step 2: Iterate through the array to check each removal for (int i = 0; i < n; i++) { int rightEvenSum; int rightOddSum; if (i % 2 == 0) { // Current element is at an even index rightEvenSum = totalEvenSum - leftEvenSum - nums[i]; rightOddSum = totalOddSum - leftOddSum; } else { // Current element is at an odd index rightEvenSum = totalEvenSum - leftEvenSum; rightOddSum = totalOddSum - leftOddSum - nums[i]; } // After removal, right part's parities are flipped // New even sum = left even sum + right odd sum // New odd sum = left odd sum + right even sum if (leftEvenSum + rightOddSum == leftOddSum + rightEvenSum) { fairCount++; } // Update left sums for the next iteration if (i % 2 == 0) { leftEvenSum += nums[i]; } else { leftOddSum += nums[i]; } } return fairCount; }}Complexity
Time
O(N), where N is the length of the input array. We perform one pass to compute the total sums and a second pass to check each index for fairness. Both passes are linear, so the total time complexity is O(N) + O(N) = O(N).
Space
O(1). We only use a few constant extra variables to store the sums, regardless of the input size.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1).
Efficiently handles large inputs without performance issues.
Cons
The logic is more complex than the brute-force approach and requires careful handling of sums.
Solutions
Solution
class Solution {public int waysToMakeFair(int[] nums) { int s1 = 0, s2 = 0; int n = nums.length; for (int i = 0; i < n; ++i) { s1 += i % 2 == 0 ? nums[i] : 0; s2 += i % 2 == 1 ? nums[i] : 0; } int t1 = 0, t2 = 0; int ans = 0; for (int i = 0; i < n; ++i) { int v = nums[i]; ans += i % 2 == 0 && t2 + s1 - t1 - v == t1 + s2 - t2 ? 1 : 0; ans += i % 2 == 1 && t2 + s1 - t1 == t1 + s2 - t2 - v ? 1 : 0; t1 += i % 2 == 0 ? v : 0; t2 += i % 2 == 1 ? v : 0; } return ans; }}/** * @param {number[]} nums * @return {number} */ var waysToMakeFair = function (nums) { let [s1, s2, t1, t2] = [0, 0, 0, 0]; const n = nums.length; for (let i = 0; i < n; ++i) { if (i % 2 == 0) { s1 += nums[i]; } else { s2 += nums[i]; } } let ans = 0; for (let i = 0; i < n; ++i) { const v = nums[i]; ans += i % 2 == 0 && t2 + s1 - t1 - v == t1 + s2 - t2; ans += i % 2 == 1 && t2 + s1 - t1 == t1 + s2 - t2 - v; t1 += i % 2 == 0 ? v : 0; t2 += i % 2 == 1 ? v : 0; } return ans; };class Solution {public: int waysToMakeFair(vector<int> &nums) { int s1 = 0, s2 = 0; int n = nums.size(); for (int i = 0; i < n; ++i) { s1 += i % 2 == 0 ? nums[i] : 0; s2 += i % 2 == 1 ? nums[i] : 0; } int t1 = 0, t2 = 0; int ans = 0; for (int i = 0; i < n; ++i) { int v = nums[i]; ans += i % 2 == 0 && t2 + s1 - t1 - v == t1 + s2 - t2; ans += i % 2 == 1 && t2 + s1 - t1 == t1 + s2 - t2 - v; t1 += i % 2 == 0 ? v : 0; t2 += i % 2 == 1 ? v : 0; } return ans; }};class Solution: def waysToMakeFair(self, nums: List[int]) -> int: s1, s2 = sum(nums[:: 2]), sum(nums[1:: 2]) ans = t1 = t2 = 0 for i, v in enumerate(nums): ans += i % 2 == 0 and t2 + s1 - t1 - v == t1 + s2 - t2 ans += i % 2 == 1 and t2 + s1 - t1 == t1 + s2 - t2 - v t1 += v if i % 2 == 0 else 0 t2 += v if i % 2 == 1 else 0 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.