Scale Engineer

Ways to Make a Fair Array

Med
#1527Time: 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.5 companies
Patterns
Prefix Sum
Data structures
Array
Companies
DoorDashNvidiaPhonePeTwilio

Prompt

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

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

  1. Initialize a counter fairCount to 0.
  2. Iterate through each index i from 0 to n-1, where n is the length of nums.
  3. For each i, create a new temporary list or array by removing the element nums[i].
  4. Initialize evenSum and oddSum to 0.
  5. Iterate through the temporary array. For each element at index j:
    • If j is even, add the element to evenSum.
    • If j is odd, add the element to oddSum.
  6. After iterating through the temporary array, check if evenSum equals oddSum.
  7. If they are equal, increment fairCount.
  8. 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]:

  1. Remove index 0: New array is [1,6,4]. Even sum (1+4)=5, Odd sum (6)=6. Not fair.
  2. Remove index 1: New array is [2,6,4]. Even sum (2+4)=6, Odd sum (6)=6. Fair. Increment count.
  3. Remove index 2: New array is [2,1,4]. Even sum (2+4)=6, Odd sum (1)=1. Not fair.
  4. 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.

Solutions

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;  }}

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

← Previous

Previous problem

Next →

Next problem