Maximum Ones

The Problem

Given a binary array arr (containing only 0s and 1s) and an integer k, return the maximum number of 1s found in any contiguous subarray of size exactly k.

arr = [1, 0, 1, 1, 0, 1, 1, 0],  k = 4  →  3
arr = [1, 1, 1, 1, 1],            k = 3  →  3
arr = [0, 0, 0, 0],               k = 2  →  0
arr = [1, 0, 1, 0, 1, 0, 1],     k = 3  →  2

Examples

Example 1

Input:  arr = [1, 0, 1, 1, 0, 1, 1, 0],  k = 4
Output: 3
Explanation: Subarrays of size 4:
  [1,0,1,1] → 3 ones   ← best
  [0,1,1,0] → 2 ones
  [1,1,0,1] → 3 ones   ← also 3
  [1,0,1,1] → 3 ones
  [0,1,1,0] → 2 ones

Example 2

Input:  arr = [1, 1, 1, 1, 1],  k = 3
Output: 3
Explanation: Any window of 3 consecutive 1s gives the maximum of 3.

Example 3

Input:  arr = [0, 0, 0, 0],  k = 2
Output: 0
Explanation: No 1s in the array — every window has 0 ones.

Intuition

Each element is either a 1 or a 0. The aggregate we care about is the count of 1s in the current window, not the sum of all elements. When the window slides:

A 1 enters from the right → ones_count += 1
A 1 leaves from the left → ones_count -= 1
A 0 entering or leaving changes nothing

This is the fixed sliding window template with a count aggregate instead of a sum aggregate. The mechanics are identical — only the add and remove operations differ.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  subgraph W1["Window [1,0,1,1]: ones=3"]
    direction LR
    A["1"] --- B["0"] --- C["1"] --- D["1"] --- E["0"] --- F["1"] --- G["1"] --- H["0"]
    PS1(["start=0"]) --> A
    PE1(["end=3"]) --> D
  end
  subgraph W2["Window [0,1,1,0]: ones=2"]
    direction LR
    A2["1✗"] --- B2["0"] --- C2["1"] --- D2["1"] --- E2["0"] --- F2["1"] --- G2["1"] --- H2["0"]
    PS2(["start=1"]) --> B2
    PE2(["end=4"]) --> E2
  end
  W1 -->|"remove arr[0]=1 (-1), add arr[4]=0 (+0) → ones=2"| W2

Sliding the window right: remove the outgoing element's contribution to the ones count, add the incoming element's contribution. The max ones count is tracked across all windows.

Brute Force: Nested Loops, O(N × k)

from typing import List

def max_ones_brute(arr: List[int], k: int) -> int:
    n        = len(arr)
    max_ones = 0

    # Try every valid starting position
    for i in range(n - k + 1):
        ones = 0

        # Count 1s in the window of size k starting at i
        for j in range(k):
            if arr[i + j] == 1:
                ones += 1

        max_ones = max(max_ones, ones)

    return max_ones

print(max_ones_brute([1, 0, 1, 1, 0, 1, 1, 0], 4))  # 3
print(max_ones_brute([1, 1, 1, 1, 1], 3))            # 3

Solution

from typing import List

class Solution:
    def max_ones_in_window(self, arr: List[int], k: int) -> int:
        # Initialize the window boundaries
        start    = 0
        end      = 0
        # Running count of 1s in the current window
        ones     = 0
        max_ones = 0

        while end < len(arr):
            # ① Expand: if the incoming element is 1, increment the ones count
            if arr[end] == 1:
                ones += 1

            # ② Contract: if window grew past k, evict the outgoing element
            if end - start + 1 > k:
                # Remove the outgoing element's contribution to the ones count
                if arr[start] == 1:
                    ones -= 1
                start += 1

            # ③ Process: when window is exactly k, update the maximum ones count
            if end - start + 1 == k:
                max_ones = max(max_ones, ones)

            end += 1

        return max_ones


sol = Solution()
print(sol.max_ones_in_window([1, 0, 1, 1, 0, 1, 1, 0], 4))  # 3
print(sol.max_ones_in_window([1, 1, 1, 1, 1], 3))            # 3
print(sol.max_ones_in_window([0, 0, 0, 0], 2))               # 0
print(sol.max_ones_in_window([1, 0, 1, 0, 1, 0, 1], 3))      # 2
print(sol.max_ones_in_window([1], 1))                        # 1

Dry Run — Example 1

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

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

start=0, end=0, ones=0, max_ones=0

end=0: ① arr[0]=1 → ones=1. size=1, not k.
end=1: ① arr[1]=0 → ones=1. size=2, not k.
end=2: ① arr[2]=1 → ones=2. size=3, not k.
end=3: ① arr[3]=1 → ones=3. ③ size=4==k → max_ones=3.
end=4: ① arr[4]=0 → ones=3. ② size=5>k → arr[0]=1 → ones=2, start=1. ③ size=4==k → max_ones=3.
end=5: ① arr[5]=1 → ones=3. ② size=5>k → arr[1]=0 → ones=3, start=2. ③ size=4==k → max_ones=3.
end=6: ① arr[6]=1 → ones=4. ② size=5>k → arr[2]=1 → ones=3, start=3. ③ size=4==k → max_ones=3.
end=7: ① arr[7]=0 → ones=3. ② size=5>k → arr[3]=1 → ones=2, start=4. ③ size=4==k → max_ones=3.
end=8: end >= n=8 → loop exits.

Return: 3 ✓

Windows checked: [1,0,1,1]=3, [0,1,1,0]=2, [1,1,0,1]=3, [1,0,1,1]=3, [0,1,1,0]=2
Max is 3, found in three different windows.

Complexity Analysis

	Complexity	Reasoning
Time	O(N)	`end` visits each element once; `start` moves at most N times total
Space	O(1)	Two pointer variables plus a count variable

Versus brute force O(N × k) — the ones count updates in O(1) per slide because only one element enters and one leaves.

Edge Cases

Scenario	Input	Output	Note
All zeros	`[0,0,0,0]`, k=2	`0`	No 1s anywhere — max stays 0
All ones	`[1,1,1,1]`, k=3	`3`	Every window is full of 1s
k == n	`[1,0,1]`, k=3	`2`	One window: the whole array
k == 1	`[1,0,1,0]`, k=1	`1`	Best single-element window is a 1
Single element	`[1]`, k=1	`1`	One window, one 1

Maximum Ones shows that the fixed sliding window aggregate doesn’t have to be a sum — it can be a count. The add and remove operations are now conditional on the element’s value (if arr[end] == 1 / if arr[start] == 1), but the three-step template (expand → contract → process) is identical. Whenever an aggregate can update in O(1) per slide, fixed sliding window applies.

Note Book