Skip to main content
Talentd

Ways to Make a Fair Array - Solution & Explanation

MediumArrayPrefix Sum17 min readAsked at: Microsoft, Meta, DoorDash +4
Practice this problem

Problem Statement

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 1 results in nums = [6,7,4,1].
  • Choosing to remove index 2 results in nums = [6,1,4,1].
  • Choosing to remove index 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 <= 105
  • 1 <= nums[i] <= 104

Approach Overview

Problem 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 1: Prefix Sums Approach

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Sliding Window Approach

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.

Code

JavaScriptC

JavaScript

C

Complexity

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.

Try this approach in the editor →

Approach 3: Enumeration + Prefix Sum

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).

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix Sums Approach

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.

Sliding Window Approach

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.

Enumeration + Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix SumsO(n)O(n)Best for clarity during interviews and when prefix arrays make reasoning about parity shifts easier
Sliding Window / Running SumsO(n)O(1)Preferred when optimizing memory or writing a concise single-pass solution

Video Solution

Ways to Make a Fair Array || Leetcode • Pepcoding • 5,288 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Ways to Make a Fair Array easy or hard?
Ways to Make a Fair Array is rated Medium because the tricky part is recognizing that removing an element shifts index parity for all elements to its right. Once this observation is made, the prefix sum solution becomes straightforward.
Ways to Make a Fair Array Python/Java solution
Most implementations use prefix sums or running sums. Python and Java solutions typically maintain totals for even and odd indices, then update them as the loop moves forward to simulate removing each element in O(n) time.
How to solve Ways to Make a Fair Array in O(n)?
First compute total sums of elements at even and odd indices. While iterating through the array, treat the current element as removed and calculate the resulting even and odd sums using prefix or running totals. Account for the parity shift of elements to the right, then check if the sums match.
What is the best approach for Ways to Make a Fair Array?
The prefix sum approach is the most common solution. It tracks cumulative sums of even and odd indices and adjusts for the parity shift that happens after removing an element. This method runs in O(n) time and ensures each index can be evaluated in constant time.
Is Ways to Make a Fair Array asked at Google/Amazon/Meta?
This problem is commonly used in interviews at companies that test array and prefix sum concepts. Variants of parity-based prefix sum problems have appeared in interviews at companies like Amazon, Google, and Meta during algorithmic screening rounds.
What data structure is used in Ways to Make a Fair Array?
The main technique uses prefix sums stored in arrays or maintained as running variables. The underlying data structure is simply an array, combined with cumulative sum tracking to quickly compute even and odd index totals.
What is the time complexity of Ways to Make a Fair Array?
The optimal solution runs in O(n) time because the array is scanned once while maintaining prefix or running sums. Each index is evaluated in constant time after computing the required even and odd sums. Space complexity ranges from O(n) with prefix arrays to O(1) with running sums.

Ready to solve this problem?

Practice Ways to Make a Fair Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays