995. Minimum Number of K Consecutive Bit Flips

Greedy

when meet 0, we flip

T: O(nk)

class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length;
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                for (int j = i; j < i+k; j++) {
                    if (j >= n) {
                        return -1;
                    }
                    nums[j] = (nums[j]+1)%2;
                }
                result++;
            }
        }
        return result;
    }
}

/**
T: O(nk)
greedy

when meet 0, we flip k elements
in the end, if flip k is out of boundary, it must -1
(why this greedy ok? if in order to flip some 0, and we flip some 1 before 0, 
it would't be better because we might to handle more flips in the begining, it's a chain reaction!)

0 0 0 1 0 1 1 0
-----     
        1 0 0
          

0 0 0 1 1 2 3 3
but T: O(nk) will be TLE

-> better solution, sweep line

k = 3
0 0 0 1 0 1 1 0
+      
      -
 */

use diff array

T: O(n)

S: O(n)

class Solution {
/** 
    [0,0,0,1,0,1,1,0], k = 3
diff[0,0,0,0,0,0,0,0]
currentFlip = 0
result = 0

currentFlip = 1
result = 1
diff[0,0,0,-1,0,0,0,0,0]

1+0 = 1 (in next round it's all 1, so our flip works!)
1+0 = 1
diff [0, 0, 0, -1, 0, 0, 0 ,0, 0]
      x. x. x   n
currentFlip += diff[i] = 1-1 = 0 -> so no flip now
then A[i] + currentFlip) % 2 = (1 + 0) % 2 = 1
-> no flip
      currentFlip = 0 
      result = 1        
diff [0, 0, 0, -1, 0, 0, 0 , -1, 0]
     [0, 0, 0, 1,  0, 1, 1,  0]
                   f
  A[i] + currentFlip) % 2 = 0 + 0 ) % 2= 0
  do flip
    currentFlip = 1
    result = 2
      0. 1  2. 3.  4. 5
diff [0, 0, 0, -1, 0, 0, 0 ,-1, -1]
     [0, 0, 0, 1,  0, 1, 1,  0]
                      f
 currentFlip + diff[i] = 1
 1 + num[i](1) = 2    %2 = 0
 do flip
    currentFlip = 2
    result 3  
diff [0, 0, 0, -1, 0, 0, 0 ,-1, -1]
     [0, 0, 0, 1,  0, 1, 1,  0]
                         n
  currentFlip + diff[i] = 2 + 0 = 2
  2+ 1 = 3 %2 = 1

diff [0, 0, 0, -1, 0, 0, 0 ,-1, -1]
     [0, 0, 0, 1,  0, 1, 1,  0]
                             n
2 - 1 = 1
1 + 0 = 1 % 2 = 1 -> no flip
-> end!
so result = 3                                                        
**/
    public int minKBitFlips(int[] A, int K) {
        int n = A.length;
        int[] diff = new int[n + 1];  // Difference array to track flips
        int flipCount = 0;            // Number of flips performed
        int currentFlip = 0;          // Current number of flips at position i
        
        for (int i = 0; i < n; i++) {
            currentFlip += diff[i];
            // System.out.println("currentFlip:" + currentFlip);
            // System.out.println("diff:" + Arrays.toString(diff));
            // If A[i] is 0 and we have even number of flips or A[i] is 1 and we have odd number of flips
            if ((A[i] + currentFlip) % 2 == 0) {
                //System.out.println(i);
                if (i + K > n) { // 5+3 = 8 == n
                    return -1;  // Impossible to flip the subarray of length K
                }
                flipCount++;
                currentFlip++; // why only need add in this variable? because this has continuous 效力 just like diff[i] to diff[i+k-1] all add 1 
                // so we only need to minus in diff[i+k]--, then next we do the currentFlip += diff[i]; it will eliminate the 1 
                diff[i + K]--;  // To revert the effect of the flip after K steps
            }
        }
        
        return flipCount;
    }
}

/**
T: O(n)
currentFlip = 0
diff [0, 0, 0]
==0 -> do flip
flipCount = 1
currentFlip = 1
diff[i+k] = diff[1]--;
diff [0, -1, 0]
[0,1,0]
currentFlip + -1 = 1 -1 = 0
1+0 = 1 pass



[0,0,0,1,0,1,1,0], k = 3

currentFlip = 0
flipCount
diff [0, 0, 0, 0, 0, 0, 0 ,0]


---------
T: O(nk)
greedy

when meet 0, we flip k elements
in the end, if flip k is out of boundary, it must -1
(why this greedy ok? if in order to flip some 0, and we flip some 1 before 0, 
it would't be better because we might to handle more flips in the begining, it's a chain reaction!)

0 0 0 1 0 1 1 0
-----     
        1 0 0
          

0 0 0 1 1 2 3 3
but T: O(nk) will be TLE

-> better solution, sweep line

k = 3
0 0 0 1 0 1 1 0
+      
      -
 */