Maximize Number of 1's

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

Maximize 1s in binary array row by flipping at most one segment.

See our study guide for structured GFG and LeetCode practice.

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?