Ways to Make a Fair Array

Medium
1139.

Ways to Make a Fair Array

Ways to Make a Fair Array is a medium coding problem on arrays and prefix sum, asked in Amazon and Google interviews.

You will delete exactly one element of nums; the elements after it shift one place to the left, so their indices change parity.

An array is fair if the sum of its even-indexed elements equals the sum of its odd-indexed elements.

Return the number of indices whose removal leaves a fair array.

Example 1

Input
nums = [1,2,1,2,2]
Output
1
Explanation
Removing index 1 leaves `[1,1,2,2]`: even positions sum to 3 and odd positions to 3.

Example 2

Input
nums = [4,4,4,4,4]
Output
5
Explanation
Any removal leaves four 4s, split 8 and 8.

Example 3

Input
nums = [7]
Output
1
Explanation
Removing the only element leaves an empty array, where both sums are 0.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var waysToMakeFair = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Ways to Make a Fair Array — Solution in Python, Java & C++

Ways to Make a Fair Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Ways to Make a Fair Array is a medium coding problem on arrays and prefix sum, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Prefix Sum
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You will delete exactly one element of nums; the elements after it shift one place to the left, so their indices change parity.

An array is fair if the sum of its even-indexed elements equals the sum of its odd-indexed elements.

Return the number of indices whose removal leaves a fair array.

Example 1

Input: nums = [1,2,1,2,2]
Output: 1
Explanation: Removing index 1 leaves `[1,1,2,2]`: even positions sum to 3 and odd positions to 3.

Example 2

Input: nums = [4,4,4,4,4]
Output: 5
Explanation: Any removal leaves four 4s, split 8 and 8.

Example 3

Input: nums = [7]
Output: 1
Explanation: Removing the only element leaves an empty array, where both sums are 0.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4

Hints for Ways to Make a Fair Array

  1. Hint 1

    Removing index i leaves the elements before i where they were, and flips the parity of every element after i.

  2. Hint 2

    Keep prefix sums of the even-indexed and odd-indexed elements.

  3. Hint 3

    After removing i: new even sum = (even sum before i) + (odd sum after i), and new odd sum = (odd sum before i) + (even sum after i).

How to solve Ways to Make a Fair Array

Deleting index i swaps the roles of even and odd positions to its right, so the new sums are prefix sums on the left combined with crossed suffix sums on the right.

Approach

  1. Compute totalEven and totalOdd, the sums over even and odd indices.
  2. Sweep i from left to right with leftEven and leftOdd covering indices < i.
  3. The right side (indices > i) has rightEven = totalEven - leftEven - (nums[i] if i is even) and rightOdd likewise.
  4. Index i works if leftEven + rightOdd == leftOdd + rightEven; then add nums[i] to the matching left sum.

Why it works

Elements left of i keep their indices; each element right of i moves one place left, so even becomes odd and vice versa. The two expressions are exactly the even and odd sums of the array after deletion.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Recomputing the sums for each removal is O(n^2).
  • Exclude nums[i] itself from the right-side sums.
  • A single-element array counts as one way: the empty array is fair.

Reference solution

Python

from typing import List

def waysToMakeFair(nums: List[int]) -> int:
    total_even = sum(nums[0::2])
    total_odd = sum(nums[1::2])
    left_even = left_odd = 0
    ways = 0
    for i, v in enumerate(nums):
        right_even = total_even - left_even - (v if i % 2 == 0 else 0)
        right_odd = total_odd - left_odd - (v if i % 2 == 1 else 0)
        if left_even + right_odd == left_odd + right_even:
            ways += 1
        if i % 2 == 0:
            left_even += v
        else:
            left_odd += v
    return ways

Java

public static int waysToMakeFair(int[] nums) {
    int totalEven = 0, totalOdd = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i % 2 == 0) totalEven += nums[i]; else totalOdd += nums[i];
    }
    int leftEven = 0, leftOdd = 0, ways = 0;
    for (int i = 0; i < nums.length; i++) {
        int rightEven = totalEven - leftEven - (i % 2 == 0 ? nums[i] : 0);
        int rightOdd = totalOdd - leftOdd - (i % 2 == 1 ? nums[i] : 0);
        if (leftEven + rightOdd == leftOdd + rightEven) ways++;
        if (i % 2 == 0) leftEven += nums[i]; else leftOdd += nums[i];
    }
    return ways;
}

C++

int waysToMakeFair(vector<int>& nums) {
    int n = nums.size();
    int totalEven = 0, totalOdd = 0;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) totalEven += nums[i]; else totalOdd += nums[i];
    }
    int leftEven = 0, leftOdd = 0, ways = 0;
    for (int i = 0; i < n; i++) {
        int rightEven = totalEven - leftEven - (i % 2 == 0 ? nums[i] : 0);
        int rightOdd = totalOdd - leftOdd - (i % 2 == 1 ? nums[i] : 0);
        if (leftEven + rightOdd == leftOdd + rightEven) ways++;
        if (i % 2 == 0) leftEven += nums[i]; else leftOdd += nums[i];
    }
    return ways;
}

JavaScript

var waysToMakeFair = function(nums) {
    var totalEven = 0, totalOdd = 0;
    for (var i = 0; i < nums.length; i++) {
        if (i % 2 === 0) totalEven += nums[i]; else totalOdd += nums[i];
    }
    var leftEven = 0, leftOdd = 0, ways = 0;
    for (var j = 0; j < nums.length; j++) {
        var rightEven = totalEven - leftEven - (j % 2 === 0 ? nums[j] : 0);
        var rightOdd = totalOdd - leftOdd - (j % 2 === 1 ? nums[j] : 0);
        if (leftEven + rightOdd === leftOdd + rightEven) ways++;
        if (j % 2 === 0) leftEven += nums[j]; else leftOdd += nums[j];
    }
    return ways;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum