Sliding Window: Given an array, count maximum number of ones

Coding Interview Questions

1 min read

Problem Statement:

You are given a binary array, return the maximum number of consecutive 1s.

Example:

Input: nums = [1, 1, 0, 1, 1, 1, 1]

Output: 4

Solution Explanation:

Solution is very simple.

We will use sliding window approach to solve the problem.

We will take 2 variables, i and j.

i will be used for the window, j is used to track the value 0.

If we encounter 0, we reset the value and calculate the max window size.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
using namespace std;


int solution(vector<int> &nums) 
{
    int i = 0;
    int j = 0;
    int maxcount=0;
    int n = nums.size();

    while(j<n)
    {
        
        if(nums[j] == 0)
        {
            i = j+1;
        }
        
        maxcount = max(maxcount, j-i+1);
        j++;
    }

    return maxcount; 
}


int main()
{

    vector<int> arr = { 1, 1, 0, 1, 1, 1, 1 };

    cout << solution(arr);
}