Flip to Maximize 1s

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Find the longest subarray of 1s if you can flip one 0. Equivalent to longest subarray with at most one 0.

Algorithm

1Sliding window with at most one 0. Track last position of 0.
2When second 0 found: move left pointer past previous 0.

Common Pitfalls

•If no 0 exists: return n (all 1s already). Track previous 0 position for correct left pointer update.

Flip to Maximize 1s.java

Java


// Approach: Kadane's-style greedy scan to find the best subarray to flip.
// Count all existing 1s as the baseline (mini). Run a second pass tracking a
// running score: +1 for each 0 (gains a 1 when flipped) and -1 for each 1 (loses a
// 1 when flipped). Reset the window whenever the running score drops to the baseline
// (no net gain). The maximum running score seen is the best achievable 1-count.
// Time: O(n) Space: O(1)
class Solution {

    int maxOnes(int[] arr) {
        int maxi = 0;
        for (int a : arr) {
            if (a == 1) {
                maxi++;
            }
        }

        int mini = maxi;
        int cur = mini;
        for (int a : arr) {
            if (cur <= mini && a == 1) {
                cur = mini; 
            }else if (a == 1) {
                cur--; 
            }else {
                cur++;
            }
            maxi = Math.max(maxi, cur);
        }
        
        return maxi;
    }
};

Was this solution helpful?