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.

Description Hints 2 Solution Video 22:07

1664. Ways to Make a Fair Array

Medium67.8% acceptance7 companies

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 <= 10⁵
1 <= nums[i] <= 10⁴

Asked at 7 companies

Dunzo Flatiron Health Twilio PhonePe DoorDash Microsoft Meta

Topics

Array Prefix Sum

Hints open one at a time

Hint 1

The parity of the indices after the removed element changes.

Hint 2

Calculate prefix sums for even and odd indices separately to calculate for each index in O(1).

22:07

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def waysToMakeFair(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[2,1,6,4]

Input

[1,1,1]

Input

[1,2,3]

Your code is saved on this device.Solution