1004. Max Consecutive Ones III
Problem Setting¶
Given an array A
of 0s and 1s, we may change up to K
values from 0 to 1.
Return the length of the longest (contiguous) subarray that contains only 1s.
Variable  Type  Description 

A  list  an array of 0s and 1s e.g., 111000 
K  int  the maximum number of changes fliping from 0 to 1 
Example 1¶
Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation: [1,1,1,0,0,1*,1,1,1,1,1*]
Numbers with * (astarisk) were flipped from 0 to 1. The longest subarray is indicated as a line of bold numers.
Example 2¶
Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: [0,0,1,1,1*,1*,1,1,1,1*,1,1,0,0,0,1,1,1,1]
Numbers with * (astarisk) were flipped from 0 to 1. The longest subarray is indicated as a line of bold numers.
Note:
1 <= A.length <= 20000
0 <= K <= A.length
A[i] is 0 or 1
In [1]:
class Solution(object):
def longestOnes(self, A, K):
i=0;n=len(A);j=0
countk=K;res=float('inf')
while j<n and i<n:
if A[j]==1:
pass
else:
if countk>0:
countk=1
else:
while countk<0 or A[i]==1:
if A[i]==0:
countk+=1
i+=1
i+=1
res=max(res,ji+1)
j+=1
return res
In [2]:
# Example 1
A = [1,1,1,0,0,0,1,1,1,1,0]
K = 2
s = Solution()
s.longestOnes(A, K)
Out[2]:
In [3]:
# Example 2
A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
K = 3
s = Solution()
s.longestOnes(A, K)
Out[3]:
Stepbystep understanding¶
 Initialization
Variable  Description 

i  the first counter to keep the pointer for the beggining of consecutive subarray of 1s 
j  the first counter to keep the pointer for the end of consecutive subarray of 1s 
n  the length of a given array A

countK  the reverse counter to count down the number of flip 
res  the result integer starting from negative infinity


the first
while
loop
i
is set as a starting point
j
(end) is increased until the length of array or using the maximum number of changes  if
j
is1
then, skip to next  if
j
is0
then, subtract the number fromcountK
Continue the above loop till
countK
becomes0


 When the
countK
becomse0
, reset the process and move the position ofi
forward+1
 if the next position is
0
then revert thecountK
and add+1
 if the next position is
1
then simply move the index ofi
forward+1
without changingcountK
 if the next position is
In [4]:
A = [1,1,1,0,0,0,1,1,1,1,0]
K = 2
i=0;n=len(A);j=0
countk=K;res=float('inf')
while j<n and i<n:
print('While loop start')
if A[j]==1:
pass
else:
if countk>0:
countk=1
else:
print('Running out countK')
while countk<0 or A[i]==1:
print('Revert the countK for the number of 1')
if A[i]==0:
countk+=1
print('Move i position forward')
i+=1
print('Move i position forward')
i+=1
print('Found the consecutive sequence %i' % int(ji+1))
print('Leave the max value between %.f and %i => leave %.f' % (res, int(ji+1), max(res,ji+1)))
res=max(res,ji+1)
j+=1
print()
print('='*40)
print('All exploration is finished')
print('Final result is %.f' % res)
Comments
Comments powered by Disqus