actually does to our total count of 1s:
- When we flip a
0, we gain a 1. (Net change: +1)
- When we flip a
1, we lose a 1. (Net change: -1)
This means we don't need to count the final 1s directly. We just need to find the contiguous subarray that gives us the maximum net gain. Finding the contiguous subarray with the maximum sum is the exact problem Kadane's Algorithm was built to solve!
The formula for our final answer becomes beautifully simple:
Total 1s = (Initial count of 1s) + (Maximum net gain from a flip)
The Step-by-Step Approach
- Count the Baseline: First, we iterate through the array to count how many
1s we start with.
- Early Exits (Optimizations): If the array is entirely
0s, flipping the whole array gives us length 1s. If the array is entirely 1s, or only has a single 0, doing zero flips (or flipping that one 0) already maxes out our possible 1s. We can return length immediately and save processing time.
- Apply Kadane's: We iterate through the array again. We treat every
0 as a 1 (potential gain) and every 1 as a -1 (potential loss). We use Kadane's algorithm to keep a running sum and track the maximum peak.
The Java Solution
Here is the highly optimized O(N) solution utilizing O(1) space:
class Solution {
int maxOnes(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int length = arr.length;
int oneCount = 0;
// Step 1: Count initial 1s - O(N)
for (int num : arr) {
oneCount += num == 1 ? 1 : 0;
}
// Step 2: Handle edge cases where max possible 1s is already guaranteed
// - No 1s (flip everything)
// - All 1s (0 operations needed)
// - Only one 0 (flip the single 0)
if (oneCount == 0 || oneCount == length || oneCount == length - 1) {
return length;
}
// Step 3: Find the maximum net gain using Kadane's Algorithm - O(N)
int maximumSum = getMaximumSum(arr);
// Calculate the final total
int totalCount = oneCount + maximumSum;
return totalCount < 0 ? 0 : totalCount;
}
private int getMaximumSum(int[] arr) {
int runningSum = 0;
int maximumSum = Integer.MIN_VALUE;
for (int num : arr) {
// Transform: 0 becomes +1 (gain), 1 becomes -1 (loss)
runningSum += num == 1 ? -1 : 1;
maximumSum = Math.max(maximumSum, runningSum);
// If our running sum drops below zero, it's a net loss.
// We reset it to 0, effectively starting a new subarray.
if (runningSum < 0) {
runningSum = 0;
}
}
return maximumSum;
}
}
Complexity Analysis
Time Complexity: O(N)
We iterate through the array exactly twice—once to count the initial 1s, and once to calculate the maximum sum. O(2N) simplifies to O(N).
Space Complexity: O(1)
We only use a few primitive integer variables (oneCount, runningSum, maximumSum) to keep track of our state, regardless of how large the input array is.