LeetCode_1037_Minimum Number of K Consecutive Bit Flips (Java)

1037. Minimum Number of K Consecutive Bit Flips

Hard

---

You are given a binary array nums and an integer k.

A k-bit flip is choosing a subarray of length k from nums and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of k-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

A subarray is a contiguous part of an array.

 

Example 1:

 Input: nums = [0,1,0], k = 1
 Output: 2
 Explanation: Flip nums[0], then flip nums[2].
 

Example 2:

 Input: nums = [1,1,0], k = 2
 Output: -1
 Explanation: No matter how we flip subarrays of size 2, we cannot make the array become [1,1,1].
 

Example 3:

 Input: nums = [0,0,0,1,0,1,1,0], k = 3
 Output: 3
 Explanation: 
 Flip nums[0],nums[1],nums[2]: nums becomes [1,1,1,1,0,1,1,0]
 Flip nums[4],nums[5],nums[6]: nums becomes [1,1,1,1,1,0,0,0]
 Flip nums[5],nums[6],nums[7]: nums becomes [1,1,1,1,1,1,1,1]
 

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= k <= nums.length

문제 풀이

코드

 class Solution {
     public int minKBitFlips(int[] nums, int k) {
         int left = 0;
         int[] prefixSum = new int[nums.length + 1];
         int cnt = 0;
         int currSum = 0; // 이전 뒤집기 기억해서 지금칸에 몇번 뒤집을지 0~k번 중 반영해야함
 
         for (int i = 0; i < nums.length; i++) {
             currSum += prefixSum[i];
 
             int currState = (nums[i] + currSum) % 2;
 
             if (currState != 1) {
                 if (i > nums.length - k) {
                     return -1;
                 }
 
                 cnt++;
 
                 prefixSum[i]++;
                 prefixSum[i + k]--;
 
                 currSum++;
             }
         }
 
         return cnt;
     }
 }