Java  

Flip to Maximize 1s in an Array

The Flip to Maximize 1s problem is a classic algorithm problem often asked in coding interviews. The task is:

Given an array of 0s and 1s, you are allowed to flip at most one contiguous subarray (change 0 → 1 and 1 → 0). Return the maximum number of 1s that can be obtained after this operation.

Problem Example

Example 1:

Input: arr = [1, 0, 0, 1, 0]
Output: 4

Explanation:

  • By flipping the subarray [0, 0] at indices 1 to 2, the array becomes [1, 1, 1, 1, 0].

  • Total 1s = 4 (maximum possible with one flip).

Example 2:

Input: arr = [1, 1]
Output: 2

Explanation:

  • Array already has all 1s.

  • Flipping any subarray would reduce the number of 1s, so the optimal choice is to flip nothing.

  • Total 1s = 2.

Key Insight

To solve the problem efficiently:

  1. Flipping 0 → 1 increases the number of 1s by +1.

  2. Flipping 1 → 0 decreases the number of 1s by -1.

If we create a gain array where:

  • gain[i] = 1 if arr[i] == 0

  • gain[i] = -1 if arr[i] == 1

Then, finding the best subarray to flip is equivalent to finding the maximum sum subarray of this gain array.

We can solve this using Kadane’s Algorithm in O(n) time.

Java Implementation

class Solution {
    int maxOnes(int[] arr) {
        int n = arr.length;
        int totalOnes = 0;

        // Step 1: Count total 1s in the original array
        for (int num : arr) {
            if (num == 1) totalOnes++;
        }

        int maxGain = 0;        // maximum gain from flipping a subarray
        int currentGain = 0;    // current sum of gain subarray

        // Step 2: Find the maximum gain subarray using Kadane's algorithm
        for (int i = 0; i < n; i++) {
            int value = (arr[i] == 0) ? 1 : -1;        // gain for current element
            currentGain = Math.max(value, currentGain + value); // extend or start new subarray
            maxGain = Math.max(maxGain, currentGain);  // track maximum gain
        }

        // Step 3: Maximum 1s = original ones + maximum gain from flip
        return totalOnes + maxGain;
    }
}

How the Code Works

Step 1: Count Original Ones

for (int num : arr) {
    if (num == 1) totalOnes++;
}

  • This counts the number of 1s in the original array.

  • Example: [1, 0, 0, 1, 0] → totalOnes = 2.

Step 2: Convert to Gain and Apply Kadane's Algorithm

int value = (arr[i] == 0) ? 1 : -1;
currentGain = Math.max(value, currentGain + value);
maxGain = Math.max(maxGain, currentGain);

  • If the element is 0, flipping it gives +1 gain.

  • If the element is 1, flipping it gives -1 gain.

  • currentGain tracks the sum of the current subarray of gains.

  • maxGain tracks the maximum sum subarray, i.e., the optimal flip range.

Step 3: Compute Maximum 1s

return totalOnes + maxGain;

  • The final answer = original number of 1s + maximum gain from flipping one subarray.

  • This also handles edge cases:

    • If the array has all 1s, maxGain = 0 → flipping nothing is optimal.

    • If the array has all 0s, flipping the whole array maximizes 1s.

Example Walkthrough

Input: [1, 0, 0, 1, 0]

  1. totalOnes = 2

  2. Gain array = [-1, 1, 1, -1, 1]

  3. Maximum subarray sum = 2 (indices 1-2)

  4. Maximum 1s = 2 + 2 = 4

Input: [1, 1]

  1. totalOnes = 2

  2. Gain array = [-1, -1]

  3. Maximum subarray sum = 0 (flipping decreases 1s)

  4. Maximum 1s = 2 + 0 = 2

Complexity Analysis

  • Time Complexity: O(n) → single pass for counting and finding max subarray sum

  • Auxiliary Space: O(1) → no extra arrays used, computation done on the fly

Conclusion

This approach efficiently finds the maximum number of 1s after flipping at most one subarray. Using Kadane’s Algorithm on a gain array is the key insight to solving it in linear time.

Membership not found