Max Consecutive Ones III

Medium

Apple

1 view

Topics:

ArraysSliding WindowsTwo Pointers

You are given a binary array nums and an integer k. Your task is to find the maximum number of consecutive 1's in the array if you are allowed to flip at most k 0's to 1's.

For example, consider the array nums = [1,1,1,0,0,0,1,1,1,1,0] and k = 2. The longest subarray with at most 2 flipped zeros is [1,1,1,0,0,1,1,1,1,1,1], which has a length of 6. The zeros at indices 5 and 10 are flipped.

Here's another example: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1] and k = 3. The longest subarray is [1,1,1,1,1,1,1,1,1,1], which has a length of 10.

Your goal is to write a function that efficiently determines the maximum possible length of consecutive 1's achievable with at most k flips. Consider edge cases and optimize for both time and space complexity. Explain your solution clearly, including the algorithm, time complexity, and space complexity. Provide code implementation for the optimal solution.

Max Consecutive Ones III

Medium

Apple

1 view

Topics:

ArraysSliding WindowsTwo Pointers

You are given a binary array nums and an integer k. Your task is to find the maximum number of consecutive 1's in the array if you are allowed to flip at most k 0's to 1's.

Here's another example: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1] and k = 3. The longest subarray is [1,1,1,1,1,1,1,1,1,1], which has a length of 10.

Solution

Brute Force Solution

A brute force approach would involve iterating through all possible subarrays and, for each subarray, counting the number of zeros. If the number of zeros is less than or equal to k, we calculate the length of the subarray and update the maximum length found so far.

Code (Python)

def longest_ones_brute_force(nums, k):
    max_len = 0
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            subarray = nums[i:j+1]
            zeros = subarray.count(0)
            if zeros <= k:
                max_len = max(max_len, len(subarray))
    return max_len

Time Complexity

O(n^3), where n is the length of the input array nums. This is because we have nested loops to generate all subarrays (O(n^2)), and for each subarray, we count the number of zeros (O(n)).

Space Complexity

O(1), as we're only using a constant amount of extra space.

Optimal Solution: Sliding Window

A more efficient approach is to use a sliding window technique. We maintain a window and expand it to the right. If the number of zeros in the window exceeds k, we shrink the window from the left until the number of zeros is back within the limit.

Algorithm

Initialize two pointers, left and right, to 0.
Initialize a variable zeros_count to 0 to keep track of the number of zeros in the current window.
Initialize max_len to 0 to store the maximum length of consecutive 1s.
Iterate through the array with the right pointer:
- If nums[right] is 0, increment zeros_count.
- While zeros_count is greater than k:
  - If nums[left] is 0, decrement zeros_count.
  - Increment left.
- Update max_len with the maximum of max_len and right - left + 1.
Return max_len.

Code (Python)

def longest_ones(nums, k):
    left = 0
    zeros_count = 0
    max_len = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zeros_count += 1

        while zeros_count > k:
            if nums[left] == 0:
                zeros_count -= 1
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

Time Complexity

O(n), where n is the length of the input array nums. Each element is visited at most twice (once by the right pointer and once by the left pointer).

Space Complexity

O(1), as we're only using a constant amount of extra space for variables like left, zeros_count, and max_len.

Edge Cases

If k is 0, the problem reduces to finding the longest consecutive sequence of 1s in the array.
If k is greater than or equal to the number of zeros in the array, the result is simply the length of the array.
Empty array: If the array is empty, the maximum length of consecutive 1s is 0.

Solution

Brute Force Solution

Code (Python)

def longest_ones_brute_force(nums, k):
    max_len = 0
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            subarray = nums[i:j+1]
            zeros = subarray.count(0)
            if zeros <= k:
                max_len = max(max_len, len(subarray))
    return max_len

Time Complexity

O(n^3), where n is the length of the input array nums. This is because we have nested loops to generate all subarrays (O(n^2)), and for each subarray, we count the number of zeros (O(n)).

Space Complexity

O(1), as we're only using a constant amount of extra space.

Optimal Solution: Sliding Window

Algorithm

Initialize two pointers, left and right, to 0.
Initialize a variable zeros_count to 0 to keep track of the number of zeros in the current window.
Initialize max_len to 0 to store the maximum length of consecutive 1s.
Iterate through the array with the right pointer:
- If nums[right] is 0, increment zeros_count.
- While zeros_count is greater than k:
  - If nums[left] is 0, decrement zeros_count.
  - Increment left.
- Update max_len with the maximum of max_len and right - left + 1.
Return max_len.

Code (Python)

def longest_ones(nums, k):
    left = 0
    zeros_count = 0
    max_len = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zeros_count += 1

        while zeros_count > k:
            if nums[left] == 0:
                zeros_count -= 1
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

Time Complexity

O(n), where n is the length of the input array nums. Each element is visited at most twice (once by the right pointer and once by the left pointer).

Space Complexity

O(1), as we're only using a constant amount of extra space for variables like left, zeros_count, and max_len.

Edge Cases

If k is 0, the problem reduces to finding the longest consecutive sequence of 1s in the array.
If k is greater than or equal to the number of zeros in the array, the result is simply the length of the array.
Empty array: If the array is empty, the maximum length of consecutive 1s is 0.