Ways to Make a Fair Array

Ways to Make a Fair Array

What is this problem about?

An array is considered "fair" if the sum of elements at even indices is equal to the sum of elements at odd indices. In this problem, you are asked to find how many indices you can remove such that the resulting array becomes fair. When an element is removed, all elements to its right shift by one position, which effectively swaps their "even/odd" status.

Why is this asked in interviews?

This coding problem is common in interviews at companies like Microsoft and Twilio because it tests the optimization of prefix sums. A naive O(N^2) solution (removing each element and recalculating sums) is too slow. The challenge is to find an O(N) solution by pre-calculating information that allows you to determine the new sums in constant time for each removal.

Algorithmic pattern used

The optimal approach utilizes Prefix Sums and Suffix Sums (or running sums). By maintaining the total sum of even and odd indices before and after a specific point, you can calculate the new totals instantly. Specifically, for an index i, the new even sum is (even sum before i) + (odd sum after i). Similarly, the new odd sum is (odd sum before i) + (even sum after i).

Example explanation

Array: [1, 2, 3].

• Remove index 0: Remaining is [2, 3]. Even sum = 2, Odd sum = 3. Not fair.
• Remove index 1: Remaining is [1, 3]. Even sum = 1, Odd sum = 3. Not fair.
• Remove index 2: Remaining is [1, 2]. Even sum = 1, Odd sum = 2. Not fair. Result: 0 fair arrays. Array: [2, 1, 6, 4].
• Remove index 0 (2): Remaining [1, 6, 4]. Even (1+4=5), Odd (6). No.
• Remove index 1 (1): Remaining [2, 6, 4]. Even (2+4=6), Odd (6). Fair! ... and so on.

Common mistakes candidates make

• Re-indexing confusion: Getting confused about which elements become even and which become odd after removal.
• Inefficient recalculation: Using a nested loop to calculate sums for every single removal, leading to a Time Limit Exceeded error on large inputs.
• Initialization errors: Not handling the start or end of the array correctly in the prefix sum logic.

Interview preparation tip

When you encounter an array problem where removing or changing one element affects everything to its right, think about how prefix sums can "store" the state of the array. The pattern of "parity shift" (even becomes odd) is a very common interview trick.