1664. Ways to Make a Fair Array


Problem Description

In this problem, you are given an array of integers called nums. Your task is to determine the number of ways you can remove exactly one element from the array such that, after the removal, the sum of the elements at the odd indices is equal to the sum of the elements at the even indices. The array uses 0-based indexing, which means the first element is at index 0 (even-indexed), the second element is at index 1 (odd-indexed), and so on.

Imagine you have an array like [2, 1, 3, 4]. If you remove the element at index 1 (which is the number 1), the new array would be [2, 3, 4]. In this new array, the sum of the even-indexed values (which are at indices 0 and 2) is 2 + 4 = 6, and the sum of the odd-indexed value (which is at index 1) is 3. Since those sums are not equal, this would not be a "fair" array according to the problem definition.

Intuition

The intuition behind the solution is to efficiently track the sums of odd and even indexed elements as we consider removing each element. If we just recalculated the sums each time we remove an element, it would be too slow, so we need a smarter approach.

We start by calculating the sum of all elements at even indices (s1) and the sum of all elements at odd indices (s2) for the original array. Once we have the total sums, as we iterate through each element to consider its removal, we can update our totals for what the sums would be if we removed that element.

As we remove an element, two scenarios can occur depending on whether the element is at an even or odd index:

  1. If the element is at an even index, we need to subtract that element's value from the even sum and add it to the odd sum (since all elements to the right will shift left by one index).

  2. If the element is at an odd index, we need to subtract that element's value from the odd sum and add it to the even sum.

We keep track of the running tallies of elements removed (t1 for even indices and t2 for odd indices). To avoid shifting all elements and updating all sums every time, we make adjustments based on the running tallies and the totals.

We then check if removing the current element makes the sum of even-indexed elements equal to the sum of odd-indexed elements. If so, we increment our answer count ans. The condition checks depend on the parity of the index and use the already computed sums as well as the tallies for correction.

This way, we are able to efficiently process each element and determine if its removal results in a "fair" array without having to recalculate the entire sum each time.

Learn more about Dynamic Programming patterns.

Solution Approach

The implementation of the solution revolves around the use of prefix sums, which is a common technique in array manipulation problems, to pre-calculate cumulating values and use them in an efficient way. The solution makes use of several variables: s1 and s2 to keep track of the sum of elements at even indices and odd indices respectively, ans to count the number of ways we can make the array fair, and t1 and t2 to keep track of the prefix sums (total of removed elements so far) at even and odd indices respectively.

The algorithm consists of the following steps:

  1. Calculate the initial sums of even and odd indexed elements and store them in s1 and s2.
1s1, s2 = sum(nums[::2]), sum(nums[1::2])
  1. Initialize ans, t1, and t2 to 0.

  2. Loop through each element in the nums array using their index i and value v.

  3. Inside the loop, perform checks to determine if removing the element at index i will result in a fair array:

    • Check if the index is even (i % 2 == 0). If true, compare t2 + s1 - t1 - v with t1 + s2 - t2. This check is based on the idea that, after removal, the total sum of even-indexed elements (s1) would be decreased by v, and the total sum of odd-indexed elements (s2) would need to include what was previously part of t1 before the i-th element. If the two sums are equal, there is a valid removal, so increment ans.

    • Check if the index is odd (i % 2 == 1). If true, compare t2 + s1 - t1 with t1 + s2 - t2 - v. Similar to the previous case, but in this scenario, we're removing an element from the odd indices, so we adjust s2 instead of s1, and compare against the sum of even-indexed elements plus the prefix sum t2.

1for i, v in enumerate(nums):
2    ans += i % 2 == 0 and t2 + s1 - t1 - v == t1 + s2 - t2
3    ans += i % 2 == 1 and t2 + s1 - t1 == t1 + s2 - t2 - v
4    t1 += v if i % 2 == 0 else 0
5    t2 += v if i % 2 == 1 else 0
  1. Update t1 and t2 with the value v pertaining to their respective index parities. This reflects the running sum of values that would have been removed up to index i.

  2. After the loop, ans will contain the total number of indices that could be removed to make nums fair.

The time complexity of this solution is O(n) since it makes a single pass through the array, and the space complexity is O(1), using only a constant amount of extra space for the variables defined.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following shows the order of node visit in a Breadth-first Search?

Example Walkthrough

Let's walk through an example to illustrate the solution approach using the array [2, 1, 3, 4, 0].

  1. We first calculate the initial sums of even and odd indexed elements:

    • s1 = sum of elements at even indices = 2 + 3 + 0 = 5
    • s2 = sum of elements at odd indices = 1 + 4 = 5
  2. We initialize ans, t1, and t2 to 0.

  3. We start to loop through each element in the nums array.

  4. For i = 0 (first element, value v = 2):

    • This is an even index, so we check if t2 + s1 - t1 - v equals t1 + s2 - t2.
    • That is, we check if 0 + 5 - 0 - 2 equals 0 + 5 - 0.
    • The condition is 3 == 5, which is false, so we do not increment ans.
    • We then update t1 with the value 2 (since it's an even index), so t1 becomes 2, and t2 remains 0.
  5. For i = 1 (second element, value v = 1):

    • This is an odd index, so we compare t2 + s1 - t1 with t1 + s2 - t2 - v.
    • That is, we check if 0 + 5 - 2 equals 2 + 5 - 0 - 1.
    • The condition is 3 == 6, which is false, so we do not increment ans.
    • We then update t2 with the value 1 (since it's an odd index), so t2 becomes 1, and t1 remains 2.
  6. For i = 2 (third element, value v = 3):

    • This is an even index, so the comparison is 1 + 5 - 2 - 3 on the left side and 2 + 5 - 1 on the right side.
    • The condition is 1 == 6, which is false, so ans stays the same.
    • We update t1 to 5, adding the value 3 to the previous value of 2.
  7. Continuing with this process for i = 3 and i = 4, we find that:

    • At i = 4, with value v = 0, given as an even index, the condition would be 1 + 5 - 5 - 0 on the left side and 5 + 5 - 1 on the right side, which simplifies to 1 == 9. The condition is false, so ans is still not incremented.
  8. After the loop is completed, ans contains the value 0, which indicates that there are no ways to remove a single element such that the sum of the even-indexed elements is equal to the sum of the odd-indexed elements.

Through this example, we can see that we process the array efficiently without recalculating the entire sum for every potential removal. This approach yields the correct answer with a linear time complexity.

Solution Implementation

1class Solution:
2    def waysToMakeFair(self, nums: List[int]) -> int:
3        # Calculate the initial sum of elements at even indices (odd positions) and 
4        # the sum of elements at odd indices (even positions)
5        sum_even_index, sum_odd_index = sum(nums[::2]), sum(nums[1::2])
6      
7        # Initialize counters for the number of ways to make the array fair,
8        # the running sum of elements at even indices, and odd indices
9        fair_ways_count = running_sum_even = running_sum_odd = 0
10      
11        # Enumerate over the list to consider removing each element in turn
12        for index, value in enumerate(nums):
13            # If the current index is even, check if removing the element makes the array fair
14            if index % 2 == 0:
15                # A fair array has equal sum of remaining elements at even and odd positions
16                is_fair_after_removal = (running_sum_odd + sum_even_index - running_sum_even - value ==
17                                         running_sum_even + sum_odd_index - running_sum_odd)
18                # If fair, increment the fair ways count
19                fair_ways_count += is_fair_after_removal
20            else:
21                # If the current index is odd, perform a similar check after removing the element
22                is_fair_after_removal = (running_sum_odd + sum_even_index - running_sum_even ==
23                                         running_sum_even + sum_odd_index - running_sum_odd - value)
24                fair_ways_count += is_fair_after_removal
25          
26            # Update the running sums for even and odd indices after considering each element
27            if index % 2 == 0:
28                running_sum_even += value
29            else:
30                running_sum_odd += value
31      
32        # Return the total number of ways the array can be made fair
33        return fair_ways_count
34
1class Solution {
2    public int waysToMakeFair(int[] nums) {
3        int evenSum = 0; // Sum of elements at even indices
4        int oddSum = 0;  // Sum of elements at odd indices
5        int n = nums.length;
6
7        // Calculate the initial sum of even and odd indexed numbers
8        for (int i = 0; i < n; ++i) {
9            if (i % 2 == 0) {
10                evenSum += nums[i];
11            } else {
12                oddSum += nums[i];
13            }
14        }
15
16        int tempEvenSum = 0; // Temporary sum for even indices
17        int tempOddSum = 0;  // Temporary sum for odd indices
18        int fairCount = 0;
19
20        // Check each index to see if removing it would make the array fair
21        for (int i = 0; i < n; ++i) {
22            int currentValue = nums[i];
23          
24            // If the index is even, removing it would change the balance of sums
25            if (i % 2 == 0) {
26                // Check if the sums minus the current value are equal
27                if (tempOddSum + evenSum - tempEvenSum - currentValue == tempEvenSum + oddSum - tempOddSum) {
28                    fairCount++;
29                }
30                // Update the temporary sum for the even indices
31                tempEvenSum += currentValue;
32            } else {
33                // Check if the sums minus the current value are equal
34                if (tempOddSum + evenSum - tempEvenSum == tempEvenSum + oddSum - tempOddSum - currentValue) {
35                    fairCount++;
36                }
37                // Update the temporary sum for the odd indices
38                tempOddSum += currentValue;
39            }
40        }
41
42        return fairCount; // Return result with the number of ways to make the array fair
43    }
44}
45
1#include <vector>
2
3class Solution {
4public:
5    int waysToMakeFair(std::vector<int>& nums) {
6        int sumEven = 0, sumOdd = 0; // Initialize sums of even and odd indices
7        int n = nums.size();
8      
9        // Calculate the total sum of elements at even and odd indices
10        for (int i = 0; i < n; ++i) {
11            if (i % 2 == 0) {
12                sumEven += nums[i];
13            } else {
14                sumOdd += nums[i];
15            }
16        }
17      
18        int prefixSumEven = 0, prefixSumOdd = 0; // Prefix sums for even and odd indices
19        int countFairIndices = 0; // This will hold the result — number of fair indices
20      
21        // Loop to find all indices where removing the element would make the array fair
22        for (int i = 0; i < n; ++i) {
23            int currentValue = nums[i];
24            if (i % 2 == 0) {
25                // Check if removing an element from even index makes sums equal
26                if (prefixSumOdd + (sumEven - prefixSumEven - currentValue) == (prefixSumEven + sumOdd - prefixSumOdd)) {
27                    countFairIndices++;
28                }
29                prefixSumEven += currentValue; // Update prefix sum for even index
30            } else {
31                // Check if removing an element from odd index makes sums equal
32                if ((prefixSumOdd + sumEven - prefixSumEven) == (prefixSumEven + sumOdd - prefixSumOdd - currentValue)) {
33                    countFairIndices++;
34                }
35                prefixSumOdd += currentValue; // Update prefix sum for odd index
36            }
37        }
38        return countFairIndices; // Return the result
39    }
40};
41
1/**
2 * Calculates the number of ways to delete exactly one element from the
3 * array so that the sum of the elements at the odd indices of the new array
4 * is equal to the sum of the elements at the even indices of the new array.
5 * @param {number[]} nums - The input array.
6 * @return {number} - The number of ways to make the array fair.
7 */
8var waysToMakeFair = function(nums: number[]): number {
9    // Variables to keep track of even and odd sums.
10    let evenSumOriginal: number = 0; 
11    let oddSumOriginal: number = 0; 
12    let tempEvenSum: number = 0; 
13    let tempOddSum: number = 0;
14
15    const length = nums.length;
16
17    // Calculate initial sums for even and odd indices.
18    for (let i = 0; i < length; ++i) {
19        if (i % 2 === 0) {
20            evenSumOriginal += nums[i];
21        } else {
22            oddSumOriginal += nums[i];
23        }
24    }
25
26    let fairWaysCount = 0;
27
28    // Iterate through the array and count the ways to make the array fair
29    // by testing the condition after removing each element.
30    for (let i = 0; i < length; ++i) {
31        const value = nums[i];
32      
33        // When removing an element at an even index, check if the sum without that
34        // element makes the array fair.
35        if (i % 2 === 0 && tempOddSum + evenSumOriginal - tempEvenSum - value === tempEvenSum + oddSumOriginal - tempOddSum) {
36            fairWaysCount += 1;
37        }
38
39        // When removing an element at an odd index, check if the sum without that
40        // element makes the array fair.
41        if (i % 2 === 1 && tempOddSum + evenSumOriginal - tempEvenSum === tempEvenSum + oddSumOriginal - tempOddSum - value) {
42            fairWaysCount += 1;
43        }
44
45        // Update temporary even and odd sums with the current element value.
46        tempEvenSum += i % 2 === 0 ? value : 0;
47        tempOddSum += i % 2 === 1 ? value : 0;
48    }
49
50    return fairWaysCount;
51};
52

Time and Space Complexity

The time complexity of the provided code is O(n), where n is the length of the nums list. This is because the code iterates through the list just once with a single loop, and within that loop, the operations performed (including arithmetic operations and conditional checks) are all constant time operations.

The space complexity of the code is O(1). Only a fixed number of variables (s1, s2, ans, t1, t2) are used, and their space requirement does not scale with the size of the input list nums. No additional data structures that grow with the input size are used.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄