Longest Subarray with Ones after Replacement
Mahabharata — Bhima's Phalanx — The Longest Unbroken Line of Warriors With K Cowards Replaced
K-कायरान् वीरैः स्थाप्य दीर्घतमा व्यूहः। शून्यस्थाने पूर्णं कृत्वा शक्तिमान् सः सेनापतिः॥
*By replacing K cowards with brave warriors, the longest phalanx is formed. Filling the empty places, the general becomes powerful.*
The Story
On the fourteenth day of the Kurukshetra war, Bhima commanded the left flank. His soldiers stood in a binary line: 1 for a brave warrior holding position, 0 for a soldier who had fled or been struck down. The line read like a battlefield report: `1 1 0 0 1 1 1 0 1 1 1 1 0 1 1`.
Bhima's problem: he had exactly K = 2 replacement warriors in reserve — elite soldiers who could fill any gap (0) in the line. He needed to find the longest contiguous stretch of 1s he could achieve by deploying these K replacements optimally.
"This is the same as: find the longest subarray containing at most K zeros," reported Sahadeva. "Replace those K zeros with 1s and the entire subarray becomes 1s."
"Exactly," said Bhima. "A window is valid if it contains at most K zeros. I want the longest such window."
The algorithm was clear: sliding window with a zero-counter.
"Expand the right boundary. If the new element is 0, increment the zero count. If zero count exceeds K, shrink from the left: if the element we remove was a 0, decrement the zero count. Continue shrinking until zero count ≤ K again."
Sahadeva traced through `[1,1,1,0,0,0,1,1,1,1,0]` with K=2:
- Expand: 1,1,1,0,0 — zeros=2, len=5, valid. max=5 - right=5 (0): zeros=3 > 2! Shrink: left=0 (1): not 0. zeros=3 still > 2. left=1. left=1 (1): not 0. zeros=3 still > 2. left=2. left=2 (1): not 0. zeros=3 still > 2. left=3. left=3 (0): zeros=2. Stop. left=4. Window [4..5] = [0,0], len=2. - right=6 (1): zeros=2. len=3. max=5 - right=7 (1): zeros=2. len=4. max=5 - right=8 (1): zeros=2. len=5. max=5 - right=9 (1): zeros=2. len=6. max=6 ← New max! - right=10 (0): zeros=3 > 2! Shrink: left=4 (0): zeros=2. Stop. left=5. Window [5..10] = [0,1,1,1,1,0], len=6. max=6.
Final answer: 6 (the window [0,1,1,1,1,0] with 2 zeros that we replace to get 6 consecutive 1s).
"The phalanx of length 6," Bhima confirmed, slamming his mace into the ground. "Six positions, two gaps filled by my reserves. That's our strongest formation."
"Note," Sahadeva added, "this problem is a special case of sw-6 (same letters after replacement). Here, the 'string' is binary (0s and 1s), the 'target character' is 1, and K is the replacement count. The condition (window_length - count_of_1s) ≤ K is the same as zeros_count ≤ K. Both solutions are equivalent."
"The simpler zero-counter approach is more readable for this binary case," Bhima decided. "Count zeros. If zeros exceed K, shrink from left. Track max window."
The phalanx held. The Kaurava charge broke against it. Bhima's two reserve warriors, placed at exactly the right gaps, made the line impenetrable.
This is the Sliding Window technique for finding the longest subarray with ones after replacing at most K zeros.
Sahadeva's First Instinct
Try every subarray. Count zeros. If zeros ≤ K, it's a valid window (all can be made 1s). Track maximum valid length. O(n²) time.
public int longestOnesBruteForce(int[] nums, int k) {
int maxLen = 0;
int n = nums.length;
for (int start = 0; start < n; start++) {
int zeros = 0;
for (int end = start; end < n; end++) {
if (nums[end] == 0) zeros++;
if (zeros > k) break; // Too many zeros, can't fix with k replacements
maxLen = Math.max(maxLen, end - start + 1);
}
}
return maxLen;
}Bhima's Wisdom
public int longestOnes(int[] nums, int k) {
int left = 0;
int zeros = 0; // Count of zeros in current window
int maxLen = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0) zeros++; // Expand: add to window
// Window has too many zeros — shrink from left
while (zeros > k) {
if (nums[left] == 0) zeros--; // Removing a zero from window
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// Alternative: slide without shrink (similar to sw-6's maxFreq trick)
public int longestOnesOptimized(int[] nums, int k) {
int left = 0, zeros = 0, maxLen = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0) zeros++;
if (zeros > k) {
if (nums[left] == 0) zeros--; // Slide: constant window size
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// Test
public static void main(String[] args) {
System.out.println(new Solution().longestOnes(new int[]{1,1,1,0,0,0,1,1,1,1,0}, 2)); // 6
System.out.println(new Solution().longestOnes(new int[]{0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1}, 3)); // 10
}Step-by-Step Walkthrough
nums = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1], k=3 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ right=0 (0): zeros=1, window=1 right=1 (0): zeros=2, window=2 right=2 (1): zeros=2, window=3 right=3 (1): zeros=2, window=4 right=4 (0): zeros=3, window=5. max=5 right=5 (0): zeros=4 > 3! Shrink: left=0(0): zeros=3. left=1. window=[1..5]=5. max=5 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ right=6 (1): zeros=3, window=6. max=6 right=7 (1): zeros=3, window=7. max=7 right=8 (1): zeros=3, window=8. max=8 right=9 (0): zeros=4 > 3! Shrink: left=1(0): zeros=3. left=2. window=[2..9]=8. max=8 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ right=10 (1): zeros=3, window=9. max=9 right=11 (1): zeros=3, window=10. max=10 ← FINAL MAX right=12 (0): zeros=4 > 3! Shrink: left=2(1): not 0. left=3. zeros=4 still > 3. Shrink: left=3(1): not 0. left=4. zeros=4 > 3. Shrink: left=4(0): zeros=3. left=5. window=[5..12]=8. ✅ Return 10
Deep Insight
**Why can we use `while` vs `if` for shrinking?**
The `while` version shrinks until the window is valid — correct but uses slightly more iterations. The `if` version (optimized) slides the window without shrinking: when zeros > K, we remove one element from the left (whether or not it's a 0) and move left. This keeps window size constant. The window only GROWS when we add a 1 or add a 0 but zeros ≤ k.
**Connection to sw-6:** This is a binary special case of sw-6. In sw-6, the condition is `(length - maxFreq) ≤ k` where maxFreq is the most frequent character. Here, `maxFreq` = count of 1s. `length - count_of_1s = count_of_0s`. So the condition becomes `zeros ≤ k`. Same math.
**What if k=0?** Find the longest run of consecutive 1s (no zeros allowed). The sliding window still works: any 0 immediately triggers shrinking.
**Edge cases:** - All zeros: if k ≥ n, return n. If k < n, return k (any k consecutive zeros) - All ones: return n (no zeros to worry about) - k ≥ number of zeros in entire array: return n
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | All O(n²) windows checked with zero counter |
| Optimal | O(n) | O(1) | Each element processed by left and right at most once |
Pattern Recognition
✅ Binary array, longest subarray with at most K zeros ✅ Variable window with a simple counter (not a map) ✅ Equivalent to sw-6 for binary case ✅ Expand until invalid, shrink to restore validity **LeetCode Trigger Phrases:** → "max consecutive ones" + "flip at most k zeros" → "replace at most k 0s with 1s" → "longest subarray of 1s" + "k replacements"
Bhagavad Gita 12.17
यो न हृष्यति न द्वेष्टि न शोचति न काङ्क्षति। शुभाशुभपरित्यागी भक्तिमान्यः स मे प्रियः॥
One who neither rejoices nor grieves, neither laments nor desires, who has renounced both good and evil — such a devoted person is dear to Me.
Connection: The algorithm treats 0s (cowards, voids) with equanimity — it neither rejoices at 1s nor despairs at 0s. Within the tolerance of K, it accepts zeros without distress, weaving them into the formation. When zeros exceed K, it releases them without attachment. The maximum phalanx emerges not from demanding perfection, but from wisely including imperfection within the bounds of what can be healed.