1004. Max Consecutive Ones III

[songyy5517]

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Example 1:

Input: nums = [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]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Example 2:

Input: nums = [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]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Intuition Essentially, this problem can be converted into finding the longest subarray containing less than k zeros. A straightforward idea is to use a sliding window when iterating over the raw array. Specifically, for each element in the array, we can consider it as the last element of the subarray, also the rightmost element of the sliding window. Then, we always keep a leftmost element, which can form a valid longest subsequence with the current element. This also involves Greedy thinking.

[songyy5517]

Approach: Sliding Window

1. Exception Handling;
2. Define variables:
   • left: record the leftmost element of the current window;
   • max_one: record the global maximum number of 1.
3. Iterate over the array, and take each element as the last element of the subarray: （1）If nums[i] == 0 , then subtract 1 from k; （2）if k <= 0 , move the leftmost pointer backward, and add 1 to k when the left pointer comes across 0, and stop when k >= 0; （3）Calculate the current length and compare with the global variable max_one.
4. Return the global variable max_one.

Complexity Analysis

• Time complexity: $O(N)$ , looping through the entire array costs $O(N)$ time;
• Space complexity: $O(1)$ , additionally define constant-sized variables.

[songyy5517]

class Solution {
    public int longestOnes(int[] nums, int k) {
        // Intuition: Sliding window.
        // 1. Exception Handling
        if (nums == null || nums.length == 0)
            return 0;

        // 2. Define variables
        int left = 0;
        int max_one = 0;

        // 3. Loop through the array
        for (int right = 0; right < nums.length; right++){
            // Update the right pointer
            if (nums[right] == 0)
                k --;

            // Move the left pointer when too many zeros are in the window
            while (k < 0){
                if (nums[left ++] == 0)
                    k ++;
            }

            max_one = Math.max(max_one, right - left + 1);
        }

        return max_one;
    }
}

[songyy5517]

2024/5/14