Maximum Number of 1s in a Window of Size k

Finding the Most 1s in a Window of Size k

Imagine you have a row of light switches. Each switch is either on (written as 1) or off (written as 0). A list that only contains 1s and 0s like this is called a binary array.

Now someone gives you a small frame — a window — that can only show k switches at a time. You slide this window along the row. At every spot, you count how many switches inside the window are on. Your goal is to find the highest count of 1s you can get from any single window position.

The problem in plain words

You are given:

• a binary array arr (only 1s and 0s),
• a positive whole number k (the window size).

A subarray of size k just means k numbers that sit next to each other in the array. You must look at every such group of k neighbours and return the largest number of 1s found in any one group.

Walking through Example 1

arr = [1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0],  k = 5

Let us slide a window of size 5:

• Positions 0–4: [1, 1, 1, 0, 1] → four 1s
• Positions 1–5: [1, 1, 0, 1, 0] → three 1s
• Positions 2–6: [1, 0, 1, 0, 0] → two 1s
• …and so on to the end.

The best we ever see is 4, so the answer is 4.

Walking through Example 2

arr = [1, 1, 0, 1, 0, 1, 1, 0, 1, 0],  k = 4

The window of size 4 that holds the most 1s gives us three 1s, so the answer is 3.

The smart way to count: a sliding window

A beginner might count all k numbers again for every position. But notice something: when the window moves one step to the right, only two things change — one old number leaves on the left, and one new number enters on the right. Everything in the middle stays the same.

So instead of recounting from scratch, we:

1. Count the 1s in the first window (the first k numbers). Call this count. Remember it as the best so far.
2. Slide one step: if the number that leaves is a 1, do count = count - 1. If the number that enters is a 1, do count = count + 1.
3. After each slide, compare count with the best so far and keep the larger one.
4. When the window reaches the end, the best value you kept is the answer.

This is called the sliding window technique. Because we only adjust by the two changing numbers, we walk through the array just once, which makes it fast even for very long arrays.

The function you must complete

class Solution {
public:
    int maximumOnes(vector<int> &arr, int k)
    {
    }
};

maximumOnes receives the array arr and the window size k, and must return the maximum number of 1s found in any window of size k.