995. Minimum Number of K Consecutive Bit Flips

h1ros

Feb 22, 2019, 10:11:59 PM

Problem setting¶

This problem "Minimum Number of K Consecutive Bit Flips" is one of the hard problems in LeetCode weekly contest 124. I was not able to spend the time during the contest. So let me review the solution line by line.

Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.

Return the number of permutations of A that are squareful. Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].

Note: 1 <= A.length <= 30000 1 <= K <= A.length

Example 1:¶

Input: A = [0,1,0], K = 1

Output: 2

Explanation: Flip A[0], then flip A[2].

Example 2:¶

Input: A = [1,1,0], K = 2

Output: -1

Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].

Example 3:¶

Input: A = [0,0,0,1,0,1,1,0], K = 3

Output: 3

Explanation:

Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0] Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0] Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]

Solution from Huoran Li ¶

In [3]:

import collections

class Solution:
    def minKBitFlips(self, A: 'List[int]', K: 'int') -> 'int':
        a = A
        n = len(a)
        k = K

        ans = 0
        cnt = 0
        mark = collections.deque()
        for i in range(n - k + 1):
            while cnt > 0 and i - mark[0] >= k:
                cnt -= 1
                mark.popleft()

            if cnt % 2 == 0:
                if a[i] == 0:
                    cnt += 1
                    ans += 1
                    mark.append(i)
                    a[i] = 1
                else:
                    pass
            else:
                if a[i] == 0:
                    a[i] = 1
                    pass
                else:
                    cnt += 1
                    ans += 1
                    mark.append(i)
            # print(i, a, mark)

        for i in range(n - k + 1, n):
            while cnt > 0 and i - mark[0] >= k:
                cnt -= 1
                mark.popleft()

            if cnt % 2 == 0 and a[i] == 0:
                return -1
            if cnt % 2 == 1 and a[i] == 1:
                return -1
        return ans

Step-by-step understanding¶

Overall solution:

Iterate over the array to find 0
Flip a K subarray unless Kth element is not beyond the array A
Back to 1 and continue.

Deque¶

One of the key data type used in this solution is called deque from collection module. Let's see the example how to use deque.

Deque is a list-like object but suitable for fast appends and pops.

Deque vs List Comparison¶

As you can see below, deque and list has quite similar usage. reference: https://pymotw.com/2/collections/deque.html

In [15]:

import collections

d = collections.deque('abcdefg')

print('=== Deque ===')
print(f'Deque: {d}')
print(f'Length: {len(d)}' )
print(f'Left end: {d[0]}') 
print(f'Right end: {d[-1]}')

d.remove('c')
print(f'remove(c): {d}')

=== Deque ===
Deque: deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])
Length: 7
Left end: a
Right end: g
remove(c): deque(['a', 'b', 'd', 'e', 'f', 'g'])

In [16]:

print('=== List ===')
l = list('abcdefg')

print(f'List: {l}')
print(f'Length: {len(l)}' )
print(f'Left end: {l[0]}') 
print(f'Right end: {l[-1]}')
l.remove('c')
print(f'remove(c): {l}')

=== List ===
List: ['a', 'b', 'c', 'd', 'e', 'f', 'g']
Length: 7
Left end: a
Right end: g
remove(c): ['a', 'b', 'd', 'e', 'f', 'g']

deque.popleft¶

deque.popleft removes and returns the leftmost element. The same function of pop but affect from left side, not right.

First `for` Loop¶

n is the length of an given array A, and k is the maximum number of the length of a sub array that we can flip.

In [ ]:

for i in range(n - k + 1):
    while cnt > 0 and i - mark[0] >= k:
        cnt -= 1
        mark.popleft()

    if cnt % 2 == 0:
        if a[i] == 0:
            cnt += 1
            ans += 1
            mark.append(i)
            a[i] = 1
        else:
            pass
    else:
        if a[i] == 0:
            a[i] = 1
            pass
        else:
            cnt += 1
            ans += 1
            mark.append(i)
            # print(i, a, mark)

For example 3,

In [52]:

A = [0,0,0,1,0,1,1,0]
n = len(A)
K = 3

i will be ranged around:

In [53]:

f'{[i for i in range(n - K + 1)]}'

Out[53]:

'[0, 1, 2, 3, 4, 5]'

In [54]:

k = 3
a = A
cnt = 0
ans = 0
mark = collections.deque()

for i in range(n - k + 1):
    print(f'i: {i}\ncnt: {cnt}\nans: {ans}')
    print(f'deque: {mark}')
    print(f'A: {a}')
    print()
    
    while cnt > 0 and i - mark[0] >= k:
        cnt -= 1
        mark.popleft()

    # When counter is even number
    if cnt % 2 == 0:
        if a[i] == 0:
            cnt += 1
            ans += 1
            mark.append(i)
            a[i] = 1
        else:
            pass
    # When counter is odd number
    else:
        if a[i] == 0:
            a[i] = 1
            pass
        else:
            cnt += 1
            ans += 1
            mark.append(i)

i: 0
cnt: 0
ans: 0
deque: deque([])
A: [0, 0, 0, 1, 0, 1, 1, 0]

i: 1
cnt: 1
ans: 1
deque: deque([0])
A: [1, 0, 0, 1, 0, 1, 1, 0]

i: 2
cnt: 1
ans: 1
deque: deque([0])
A: [1, 1, 0, 1, 0, 1, 1, 0]

i: 3
cnt: 1
ans: 1
deque: deque([0])
A: [1, 1, 1, 1, 0, 1, 1, 0]

i: 4
cnt: 0
ans: 1
deque: deque([])
A: [1, 1, 1, 1, 0, 1, 1, 0]

i: 5
cnt: 1
ans: 2
deque: deque([4])
A: [1, 1, 1, 1, 1, 1, 1, 0]

Second `for` loop¶

for i in range(n - k + 1, n):
    while cnt > 0 and i - mark[0] >= k:
        cnt -= 1
        mark.popleft()

    if cnt % 2 == 0 and a[i] == 0:
        return -1
    if cnt % 2 == 1 and a[i] == 1:
        return -1
return ans

In [48]:

f'{[i for i in range(n - K + 1, n)]}'

Out[48]:

'[6, 7]'

In [55]:

# Second For Loop
for i in range(n - k + 1, n):
    print(f'i: {i}\ncnt: {cnt}\nans: {ans}')
    print(f'deque: {mark}')
    print(f'A: {a}')
    print()
    
    while cnt > 0 and i - mark[0] >= k:
        cnt -= 1
        mark.popleft()

    if cnt % 2 == 0 and a[i] == 0:
#         return -1
        print('return: -1')
    if cnt % 2 == 1 and a[i] == 1:
        print('return: -1')
#         return -1
print(f'return: {ans}')
# return ans

i: 6
cnt: 2
ans: 3
deque: deque([4, 5])
A: [1, 1, 1, 1, 1, 1, 1, 0]

i: 7
cnt: 2
ans: 3
deque: deque([4, 5])
A: [1, 1, 1, 1, 1, 1, 1, 0]

return: 3