Leetcode 1664: Ways to Make a Fair Array

Input: You are given an integer array `nums`.

Example: nums = [3, 2, 7, 5]

Constraints:

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^4

Output: Return the number of indices such that after the removal, the array becomes fair.

Example: 2

Constraints:

• The array must be fair after removing one index.

Goal: To find how many indices can be removed such that the array becomes fair after removal.

Steps:

• Compute the sum of the elements at even and odd indices of the original array.

• Iterate through the array and simulate removing each index, checking if the remaining array is fair.

Goal: The constraints ensure the solution handles large arrays efficiently.

Steps:

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^4

Assumptions:

• The input array will always have at least one element.

• Input: nums = [3, 2, 7, 5]

• Explanation: The two valid indices to remove are 2 and 3 where the resulting array becomes fair.

• Input: nums = [4, 4, 4]

• Explanation: Since all elements are the same, removing any element results in a fair array.

Approach: We will use a prefix sum approach to efficiently calculate the sum of even and odd indexed elements and check for fairness after removing each index.

Observations:

• Removing an element affects both the even and odd indexed sums. We need to track these sums while removing each element.

• We can calculate the total even and odd indexed sums first, then iteratively simulate removing each element and check if the remaining sums are equal.

Steps:

• Initialize two arrays: one to track the prefix sums of even indices and the other to track odd indices.

• For each index, simulate removing it and check if the remaining sums for even and odd indices are equal.

Empty Inputs:

• The input will always have at least one element, so we do not need to handle an empty input.

Large Inputs:

• Ensure that the solution handles arrays of size up to 10^5 efficiently.

Special Values:

• If all elements in the array are the same, any index removal will lead to a fair array.

Constraints:

• The solution must be efficient for large arrays and handle the maximum constraint sizes.


int waysToMakeFair(vector<int>& nums) {

    vector<int> left(2, 0), right(2, 0);
    
    int n= nums.size(), res = 0;
    
    for(int i = 0; i < n; i++)
        right[i%2] += nums[i];
    
    for(int i = 0; i < n; i++) {
        right[i%2] -= nums[i];
        
        if(left[0] + right[1] == right[0] + left[1]) res++;
        
        left[i%2] += nums[i];
    }

    return res;
}

1 : Function Definition

int waysToMakeFair(vector<int>& nums) {

Defines the function `waysToMakeFair` which takes an integer vector `nums` and returns the number of ways the array can be made fair by removing one element.

2 : Variable Initialization

    vector<int> left(2, 0), right(2, 0);

Initializes two vectors `left` and `right` to track prefix and suffix sums for odd and even indices.

3 : Variable Initialization

    int n= nums.size(), res = 0;

Initializes `n` as the size of the input array and `res` to count the number of valid removals.

4 : Loop Initialization

    for(int i = 0; i < n; i++)

Begins a loop to calculate the initial suffix sums for odd and even indices.

5 : Suffix Sum Calculation

        right[i%2] += nums[i];

Adds the value at index `i` to the appropriate even or odd suffix sum in the `right` vector.

6 : Loop Iteration

    for(int i = 0; i < n; i++) {

Begins a loop to iterate through each element, simulating its removal and updating the prefix and suffix sums.

7 : Update Suffix Sum

        right[i%2] -= nums[i];

Subtracts the current element from the appropriate even or odd suffix sum in the `right` vector to simulate its removal.

8 : Fairness Check

        if(left[0] + right[1] == right[0] + left[1]) res++;

Checks if the prefix and suffix sums for odd and even indices are equal after removing the current element. If true, increments the result counter.

9 : Update Prefix Sum

        left[i%2] += nums[i];

Adds the current element to the appropriate even or odd prefix sum in the `left` vector.

10 : Return Result

    return res;

Returns the total number of ways to make the array fair.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) because we process each element once.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) due to the storage required for prefix sums.

Leetcode 1664: Ways to Make a Fair Array

Explore →