Max Consecutive Ones

 Leetcode - 485/487/1004

Max Consecutive Ones - I/II/III

1. Max Consecutive Ones - I

https://leetcode.com/problems/max-consecutive-ones/

Let us understand the problem with the following example. Say nums = [1, 1, 0, 1, 1, 1, 0, 1, 1]. Here the consecutive 1's lie in the following intervals - [0, 1], [3, 5] and [7, 8] each of length 2, 3 and 2 respectively. The expected result is max(2, 3, 2) = 3.

Solution 1: Process one symbol at a time - O(n) time, O(1) space

While iterating the array, if we hit a 0, that means the current streak of consecutive 1's is broken and the answer at that particular time is the max of the current streak and the previous maximum streak. Keeping this in mind, iterate the array and count the consecutive 1's and also the maximum number of consecutive 1's seen until that point and once we hit a 0, restart the current streak. 

This calls for 2 variables maxstreak and curstreak. curstreak is to be incremented upon each 1 we encounter and has to be set to 0 when we encounter an 1. maxstreak is to be updated for every 1 we encounter and the value is max of curstreak and the previous maxstreak.

    int processOneSymbolAtATime(vector<int>& nums) {
	int maxstreak = 0, curstreak = 0;
	for(int num : nums) {
	    if(num == 1) {
		++curstreak;
		maxstreak = max(maxstreak, curstreak);
	    } else {
		curstreak = 0;
	    }
	}
	return maxstreak;
    }       
 

NOTE: max(maxstreak, curstreak) has to be found for every 1 that is encountered(in if() and not just in else), otherwise the code wouldn't cover the case of maximum number of 1's at the end of the array. Eg: [1,0,1,1,0,1,1,1,1,1]. A simple fix to the later is to calculate max() once more before returning.

Complexity Analysis:

Since every element of the array is accessed only once, the time complexity would be linear i.e of the order O(n)

We donot use any extra space other than 2 variables, which gives us a constant space complexity, O(1)

Solution 2: Cycles of 1's and 0's - O(n) time, O(1) space

This method suggests that max(curstreak, maxstreak) need not be calculated for every 1 encountered with contrast to Solution 1. Rather we can have 2 variables point to beginning and ending indices of consecutive 1's or consecutive 0's. This calls for finding only the max() of only the previous maxstreak and length of the interval with consecutive 1's which can be found by subtracting end and beginning indices.

 
       int cyclesOfOnesAndZeros(vector<int>& nums) {
	    int n = nums.size();
	    int longest = 0;
	    int i = 0;
	    while(i < n) {
	        int j = i;
	        while(j < n && nums[j] == 1) ++j;
		    longest = max(longest, j - i);
		    i = j;
		    while(i < n && nums[i] == 0) ++i;
	    }
	    return longest;
	}

         

Complexity Analysis:

Eventhough we have nested while loops, every element is accessed only once giving a linear time complexity, O(n) along with constant space complexity O(1). Hence there is no improvement over Solution 1.

Solution 3: Dynamic Programming approach - O(n) time, O(1) space

We can think of Soltuion 1 with respect to a top-down DP solution as we have overlapping subproblems in the sense that the maxstreak of size n, depends on the previous maxstreak i.e. maxstreak of smaller size n-1. This can be formulated mathematically as following:

Let f(n) be the maxstreak for array of size n and g(n) represent curstreak value for array of size n.

Then,

f(n) = max{ f(n-1), g(n) } ; f(0) = 0

g(n) = g(n-1) + 1 iff nums[n-1] = 1       (streak of 1's)

g(n) = 0 iff nums[n-1] = 0                      (streak of 0's)

g(0) = 0 otherwise

 		
 	int recurrence(vector<int>& nums) {
            int f = 0;
            int g = 0;
            for(int i = 0; i < nums.size(); ++i) {
                if(nums[i] == 0) {
                    g = 0;
                } else {
                    ++g;
                    f = max(f, g);
                }
            }
            return f;
        }

Complexity Analysis:

This method has no improvement over previous solutions with linear time and constant space complexeties with the same justifications.

2. Max Consecutive Ones - II

https://leetcode.com/problems/max-consecutive-ones-ii/

Let us understand the problem with the following example. Say nums = [1, 1, 0, 1, 1, 1, 0, 1]. We have 2 0's in the list. That means we get 2 intervals after flipping these 0's individually. By flipping only the 0 at index 2 we get the interval [0, 5] of consecutive 0's with length 6 and by flipping only the 0 at index 6, we get the interval [3, 7] with length 5. The final answer would then be max(5, 6) = 6.

Solution 1: Brute-Force - O(n²) time, O(1) space

A trivial approach would be to iterate the array, and on encountering a 0, flip it to 1, find the consecutive number of 1's in the whole of resultant array(call a function which has Max Consecutive Ones - I implemented), flip it back to 0 and continue the interation and repeat the process until end of list.

 
    int bruteforce(vector<int>& nums) {
	int n = nums.size();
	if(accumulate(nums.begin(), nums.end(), 0) >= n-1)  
            return n; // at most one zero in the whole array

        int res = 0;
        for(int k = 0; k < n; ++k) {
            if(nums[k] == 1) continue;
            nums[k] = 1; // try setting it to one

            int longest = 0;
            int i = 0;
            while(i < n) {
                int j = i;
                while(j < n && nums[j] == 1) ++j;
                longest = max(longest, j - i);

                i = j;
                while(i < n && nums[i] == 0) ++i;
            }
            res = max(res, longest);

            nums[k] = 0; // undo setting it to one
        }
        return res;
    }

 

NOTE: int accumulate(begin, end, val); returns sum of the elements in the container lying in the interval [begin, end) added to val. In our code, as nums is a binary array, by sending val = 0, for only 1 zero or no zero case, the function returns a value which is either n-1 or n.

Complexity Analysis:

We get a quadratic time complexity, O(n²)  as the worst case accounts for all 0's in the array wherin for every element, we check for max consecutive 1's in the resultant array which is of time complexity O(n), which effectively makes it O(n²) for n elements.

We use no extra space and hence the code has constant space complexity.

Solution 2: Window of 3 zeros - O(n) time, O(1) space

Consider a pattern 011110111101. By flipping atmost 1 zero at a time, we get 11111011101, 01111111101 and 01111011111.  We can observe the following:

1. For the very first zero in the array at index say z1, if we find the next zero in the array at index z2, then the max consecutive 1's interval upto z2 would be [0, z2-1].

2. Once we get a third zero in the array and for every zero after that we get new consecutive 1's intervals which acts like a competition to the maximum sized interval until that point. If we have a zero at index z2 and the zero before that had occured at index z1 and zero after that occurs at index z3, then the new 1's interval would be [z1+1, z3-1]. max() of the size of the newly found interval and the old max interval size has to be calculated at the end of this step each time. 

3. For the right-most zero in the list at index z3, we need to take care of the interval [z2+1, n-1] as well.

Apart from the above mentioned 3 cases, we need to take care of the following as we donot get valid values for z1, z2 and z3 as mentioned above:

1. When there are no zeroes or exactly one zero then the output is n.

2. When there are exactly 2 zeroes at indices z1 and z2, then the output is maximum of size of intervals [z1, n-1] and [0, z2-1]. 

The implementation can be done in the following ways:

1. We can iterate once throughout the array and note down the position of 0's in the array in another array. Using this array, we can calculate the intervals as mentioned above.

2. The above implementation needs linear extra space. As we just need the position of maximum 3 zeros which are one after another for calculating a single interval, we can do the job with 3 variables which are frequently updated after every interval calculation. The interval [z1+1, ... , z2, ... z3-1] can be considered as a window with zero at nums[z2] only.

    
    int windowOf3Zeros(vector<int>& nums) {
        int n = nums.size();
        int z1 = -1, z2 = -1, z3 = -1;
        int res = 0;
        for(int i = 0; i < nums.size(); ++i) {
            if(nums[i] == 0) {
                if(z1 == -1) { // first zero
                    z1 = i;
                } else if(z2 == -1) { // second zero
                    z2 = i;
                    res = z2; // window having the first zero in the window
                } else if(z3 == -1) { // the third zero
                    z3 = i;
                    res = max(res, z3 - (z1+1)); // window having the 2nd zero in the window
                } else { // fourth or later zero
                    z1 = z2;
                    z2 = z3;
                    z3 = i;
                    res = max(res, z3 - (z1+1)); // window having nums[z2] zero in the window
                }
            }
        }
        // window having nums[z3] zero in the window
        if(z2 != -1 && z3 != -1) { 
            z1 = z2;
            z2 = z3;
            z3 = n;
            res = max(res, z3 - (z1+1));
        // only two zeros,  window having nums[z2] zero in the window
        } else if(z2 != -1 && z3 == -1) { 
            z3 = n;
            res = max(res, z3 - (z1+1));
        } else if(z2 == -1) { // no zeros at all
            res = n;
        }
        return res;
    } 

Complexity Analysis:

We iterate the array only once and hence we get a linear time complexity O(n), along with a constant space complexity O(1).

Solution 3: Sliding window one Cycle of 1's and 0's at a time - O(n) time, O(1) space

To reduce the number of edge cases to be taken care explicitly by using 3 variables, we can generalize the problem as following:

We need to find an index i with nums[i] = 0 and an index j with nums[j] = 0 such that (i, j) has exactly 1 zero in it. This can also be concluded by the fact that in Solution 2, we use the interval (z1, z3) and no z2 for interval calculation, which implies 2 variables will suffice.

To implement this method, we can have a loop invariant wherein, i initially pointed to index 0 and j initially pointed to the index such that nums[j-1]. We can skip all the 1's encountered on incrementing j until the next j such that nums[j] = 0. In the same way we can skip all the 1's encountered on incrementing i until the next i such that nums[i] = 0. This gives an interval (i, j) and check if it's length is greater the previously found intervals.

The zero at (j+1)th index guarentees that in the next iteration, the interval [i'+1, j'-1], has exactly 1 zero (where i' and j' are the values in the next iteration, after the iteration with the interval [i+1, j-1]. 

NOTE: We need to still take care of the cases before the loop invariant, wherein there are no zeros at all and there is only one zero in the whole array, as we do not get an valid value for i and j such that [i+1, j-1] is a consecutive 1's interval.

    
    int SlidingWindowOneCycleOfOnesAndZerosAtATime(vector<int>& nums) {
        int n = nums.size();
        int i = 0;
        int j = 0;
        while(j < n && nums[j] != 0) ++j;
        if(j == n) return n; // there are no zeros
        // j is pointing to the first zero
        ++j;
        while(j < n && nums[j] != 0) ++j;
        if(j == n) return n; // there is only one zero in the the array
        
        // Open range [i, j) has exactly one zero and j is pointing to a zero
        int res = j - i;
        while(j < n) { 
        // loop invariant: Open range [i, j) has exactly one zero and j is pointing to a zero
            ++j; // a second zero is in the range [i,j)
            while(j < n && nums[j] != 0) ++j;
            
            while(nums[i] != 0) ++i; // exclude the leading zeros in the window
            ++i; // exclude the left-most zero among the two zeros in the window
            res = max(res, j-i);
        }
        return res;
    }

Complexity Analysis:

We do not have a prominent improvement in the time and space complexeties as this method also accesses each element of the array exactly once with the help of no more than 2 variables, and hence takes linear and constant, time and space complexity respectively.

3. Max Consecutive Ones - III

https://leetcode.com/problems/max-consecutive-ones-iii/

Let us understand the problem with the following example. Say nums = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1]; k = 3. By flipping the 3 underlines zeros, we get [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1] with max consecutive ones as 10.

Solution 1: Brute-Force - O(n²) time, O(1) space

A trivial approach would be to iterate the array, and on encountering a 0, find the (k-1) more zeros immediately after it and flip these k zeroes, and find consecutive ones in the resultant array(Max Consecutive Ones - I), flip them all back and repeat until end of array.

Complexity Analysis:

Consider the worst case when all the elements of the arraty are 0. For each of the n-elements of the array, we need to find k-1 more zeroes, which effectively makes the algorithm O(n) until this point and to find the max consecutive ones on the resultant array, effectively makes the solution O(k*(n + k)) or O(n²) as k<=n.

We use no extra space and hence the code has constant space complexity.

Solution 2: Window of (k+2)-zeros - O(n) time, O(n) space

Analogous to solution 2 of Max Consecutive Ones - II, we can keep track of k+2 indices, say z₀, z₁, z₂ .... z_k, z_k+1, all pointing to 0's in a continious fashion and the interval [z0+1, zk+1-1] is a valid window of consecutive ones.  

Complexity Analysis:

We need O(k) or O(n) extra space as k<=n for coding this solution. It works in linear time, O(n) though.

Solution 3: Variable-width sliding window - O(n) time, O(1) space

The above problem can also be solved using a variable length sliding window and two pointer technique where we use the pointers to keep track of the starting and ending index of the variable width sliding window. This is analogous to solution 3 of Max Consecutive Ones - II. This solution is a improvement over solution 2 because of the fact that it can work with constant extra space.

We use i and j as the pointer to the starting index and ending index of the sliding window. The width of the window will be between starting index i and ending index j in the subarray. The window, [i+1, j-1], at any time should have exactly k-zeroes.

Initially i and j will be pointing to the starting index of the array, we increment j until we visit k '0's . If the given array has less than k zeros it means that we can flip all the '0's making the maxstreak the length of the array. If not, we set maxstreak to j-i and use the loop variant wherein we update maxstreak as max(maxstreak,  window length) until we visit (k+1)th '0' . When (k+1)th '0' is visited the value of i is incremented until it visits the next '0' in the subarray from i. The loop varient runs until every element of the array is visited.

    
    int longestOnes(vector<int>& nums, int k) {
        int i = 0, j = 0; // [i,j) open range -- size = j - i
        
        while(j < nums.size() && k > 0) {
            if(nums[j] == 0) --k;
            ++j;
        }
        if(j == nums.size()) return nums.size(); // all ones in nums
        
        int maxSize = j - i; // first window having a zero
        // loop invariant: the window [i, j) has exactly k zeros
        while(j < nums.size()) {
            if(nums[j] == 1) {
                ++j;
                maxSize = max(maxSize, j - i);
            } else {
                ++j;
                // excluding the ones that appear before the left-most zero
                while(nums[i] != 0) ++i; 
                ++i; // exclude the left-most among the k+1 zeros
            }
        }
        return maxSize;
    }

Complexity Analysis:

This method has a substantial improvement over bruteforce method and has a average linear time complexity O(n) and ofcourse constant space complexity, O(1) as we are not making use of extra space except some variables.