Max Consecutive Ones - Sliding Window - Visualization

Sliding Window & Two Pointer Problems

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given a binary array nums (containing only 0s and 1s), your task is to find the maximum number of consecutive 1s in the array.

If the array is empty, return 0.

Example:

Input: nums = [1,1,0,1,1,1] → Output: 3

Explanation: The longest run of consecutive 1s is from index 3 to 5.

Examples❯

nums Output Description
[1, 1, 0, 1, 1, 1] 3 Longest streak of 1s is from index 3 to 5: [1, 1, 1]
[1, 1, 1, 1] 4 All elements are 1s, entire array is the streak
[0, 0, 0] 0 No 1s present, so maximum consecutive 1s is 0
[1, 0, 1, 0, 1] 1 No consecutive 1s; each 1 is isolated
[0, 1, 1, 1, 0, 1, 1] 3 Two runs of 1s; longest one is of length 3 from index 1 to 3
[1] 1 Single element 1 forms a run of length 1
[0] 0 Single 0, so no 1s found
[] 0 Empty input array, so return 0 as per definition

Solution❯

Understanding the Problem

We are given an array of binary numbers — that means it only contains 0s and 1s.

Our task is to find the maximum number of consecutive 1s in the array. That means we need to scan the array and figure out the longest stretch where all the numbers are 1 and appear one after the other, without a 0 in between.

This is a perfect scenario to use the sliding window technique — a powerful method to scan parts of an array while maintaining some conditions (in this case, counting continuous 1s).

Step-by-Step Solution with Example

Step 1: Choose an Example

Let’s take the given example: nums = [1, 1, 0, 1, 1, 1]

We want to find the longest sequence of 1s without interruption. From looking at the array, we can see the longest streak is from index 3 to 5: [1, 1, 1], which is of length 3.

Step 2: Understand the Intuition

Imagine scanning the array with your eyes. Every time you see a 1, you continue counting. But the moment you see a 0, the count breaks, and you start over from the next number. This is the core idea behind using a sliding window.

Step 3: Initialize Variables

  • start = 0: This will mark the beginning of the current window of 1s.
  • end = 0: This will iterate through each element.
  • maxCount = 0: This keeps track of the maximum number of 1s seen so far.

Step 4: Traverse the Array

Loop until end reaches the end of the array. For each number:

  • If it is 1, that means the window is valid. Move end++.
  • If it is 0, the window breaks. Move both start and end to the next index after the zero to begin a fresh window.

At each step, update the result with maxCount = max(maxCount, end - start).

Step 5: Simulate on the Example

Array: [1, 1, 0, 1, 1, 1]

Index 0: nums[0] = 1 → window = [0-0] → length = 1 → maxCount = 1  
Index 1: nums[1] = 1 → window = [0-1] → length = 2 → maxCount = 2  
Index 2: nums[2] = 0 → break window → start = 3, end = 3  
Index 3: nums[3] = 1 → window = [3-3] → length = 1 → maxCount = 2  
Index 4: nums[4] = 1 → window = [3-4] → length = 2 → maxCount = 2  
Index 5: nums[5] = 1 → window = [3-5] → length = 3 → maxCount = 3

Step 6: Return the Result

After the loop ends, the value of maxCount is 3, which is the correct answer.

Edge Cases

  • Empty Array: If nums = [], then return 0 since there are no elements.
  • No 1s: If nums = [0, 0, 0], then the longest sequence is 0.
  • All 1s: If nums = [1, 1, 1, 1], then return the length of the array, which is 4.
  • Single Element: If nums = [1], return 1. If nums = [0], return 0.

Final Thoughts

This problem teaches you how to use a simple sliding window approach to track continuous patterns in an array. By carefully updating your start and end pointers, and maintaining a count of maximum window size, you can solve this efficiently in O(n) time without using any extra space.

Always begin by understanding the problem and walking through an example manually. That helps you build intuition, especially for edge cases.

Algorithm Steps❯

  1. Initialize two pointers: start = 0 and end = 0, and a variable maxCount = 0 to track the maximum streak of 1s.
  2. Loop while end is less than the length of the array:
  3. → If nums[end] == 1, the current window is valid, so continue expanding the window by doing end++.
  4. → If nums[end] == 0, reset the window: move start = end + 1 and increment end.
  5. → At each step, update maxCount = max(maxCount, end - start).
  6. Once the loop finishes, return maxCount as the result.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int findMaxConsecutiveOnes(int* nums, int numsSize) {
    int maxCount = 0, start = 0, end = 0;
    while (end < numsSize) {
        if (nums[end] == 1) {
            end++;
        } else {
            start = end + 1;
            end++;
        }
        if (end - start > maxCount) {
            maxCount = end - start;
        }
    }
    return maxCount;
}

int main() {
    int nums[] = {1,1,0,1,1,1};
    int size = sizeof(nums)/sizeof(nums[0]);
    int result = findMaxConsecutiveOnes(nums, size);
    printf("Max consecutive ones: %d\n", result);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)Even in the best case, such as when all elements are 1s, the algorithm must still iterate through the entire array to count them. Thus, the time complexity is linear.
Average CaseO(n)The algorithm uses a single pass through the array with two pointers. Each element is checked exactly once, so the operations grow linearly with the array size.
Worst CaseO(n)In the worst case, where 0s interrupt sequences of 1s frequently, the algorithm still performs a single pass through the array, yielding linear time complexity.

Space Complexity❯

O(1)

Explanation: The algorithm only uses a constant amount of extra space for pointers and counters (start, end, maxCount), regardless of the input size.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...