1004. Max Consecutive Ones III

Comments

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

Solution from abhi1027-%3A-Python-Sliding-window)

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,j-i+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]:
6
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]:
10

Step-by-step understanding

  1. 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

  1. 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 is 1 then, skip to next
      • if j is 0 then, subtract the number from countK

      Continue the above loop till countK becomes 0

  1. When the countK becomse 0, reset the process and move the position of i forward +1
    • if the next position is 0 then revert the countK and add +1
    • if the next position is 1 then simply move the index of i forward +1 without changing countK
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(j-i+1))
    print('Leave the max value between %.f and %i => leave %.f' % (res, int(j-i+1), max(res,j-i+1)))
    res=max(res,j-i+1)  
    j+=1
    print()

print('='*40)
print('All exploration is finished')
print('Final result is %.f' % res)

While loop start
Found the consecutive sequence 1
Leave the max value between -inf and 1 => leave 1

While loop start
Found the consecutive sequence 2
Leave the max value between 1 and 2 => leave 2

While loop start
Found the consecutive sequence 3
Leave the max value between 2 and 3 => leave 3

While loop start
Found the consecutive sequence 4
Leave the max value between 3 and 4 => leave 4

While loop start
Found the consecutive sequence 5
Leave the max value between 4 and 5 => leave 5

While loop start
Running out countK
Revert the countK for the number of 1
Move i position forward
Revert the countK for the number of 1
Move i position forward
Revert the countK for the number of 1
Move i position forward
Move i position forward
Found the consecutive sequence 2
Leave the max value between 5 and 2 => leave 5

While loop start
Found the consecutive sequence 3
Leave the max value between 5 and 3 => leave 5

While loop start
Found the consecutive sequence 4
Leave the max value between 5 and 4 => leave 5

While loop start
Found the consecutive sequence 5
Leave the max value between 5 and 5 => leave 5

While loop start
Found the consecutive sequence 6
Leave the max value between 5 and 6 => leave 6

While loop start
Running out countK
Move i position forward
Found the consecutive sequence 6
Leave the max value between 6 and 6 => leave 6

========================================
All exploration is finished
Final result is 6

Comments

Comments powered by Disqus