Maximize Number of 1's

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Maximize 1s in binary array row by flipping at most one segment. Kadane-style DP.

Algorithm

1Encode: 0->+1 (gain from flip), 1->-1 (would lose by flipping). Find max subarray sum, add to original 1-count.

Common Pitfalls

•Flipping a 0 to 1 gains +1, flipping a 1 to 0 costs -1. Kadane on this encoding gives optimal segment to flip.

Maximize Number of 1's.java

Java

// Approach: Sliding window. Find longest window of 0s/1s that can have at most one 0 flipped.
// Time: O(n) Space: O(1)
class Solution {
    public int maxOnes(int arr[], int k) {
        int left = 0, right = 0;
        int count = 0;

        for (; right < arr.length; right++) {
            if (arr[right] == 0)
                count++;
                
            if (count > k) {
                if (arr[left] == 0)
                    count--;
                left++;
            }
        }

        return right - left;
    }
}

Was this solution helpful?