Brute Force Approach

Imagine you are reading a book  and tracking your focus:

1 → Fully focused

0 → Distracted

You are allowed only K distractions

Now what you do (brute force):

You start from every page

From each page, you keep reading forward
Count how many times you get distracted
If distractions exceed K → you stop and restart from the next page

???? So basically:

You are rechecking the same pages again and again from scratch

How It Works

For every index i:

1. Start a subarray from i
2. Move forward with index j
3. Count number of zeros in [i → j]
4. If zeros ≤ K → update answer
5. If zeros > K → stop and move to next i

Dry Run Example

Check all subarrays:

• Start at index 0:
  • [1] → valid
  • [1,0] → valid (1 zero)
  • [1,0,1] → valid
  • [1,0,1,0] → ❌ invalid (2 zeros > K)
• Start at index 1:
  • [0] → valid
  • [0,1] → valid
  • [0,1,0] → ❌ invalid

...and so on.

Maximum length found = 3

Code (Brute Force)

Time & Space Complexity

• Time Complexity: O(n²)
  → Two nested loops
• Space Complexity: O(1)
  → No extra space used

Why Brute Force Fails

Here’s the problem:

It checks too many unnecessary subarrays
Recalculates zero count again and again
Becomes very slow for large inputs (like 10⁵ elements)

Intuition Gap

Notice this:

When we move from one subarray to the next, we are starting from scratch again, even though most elements are the same.

This is the inefficiency.

Key Insight Leading to Optimization

“Why not reuse previous work instead of recalculating everything?”

Instead of restarting every time:

• We can expand and shrink a window dynamically
• Keep track of zeros in real-time

This idea leads to the Sliding Window Approach (Optimal Solution)