This post is completed by 5 users

  • 3
 Add to List
Medium

545. Maximizing Contiguous Ones with a Single Flip in a Binary Array

Objective: Determine the length of the longest contiguous sequence of ones in a binary array while permitting a single flip from 0 to 1

Examples: 

Example 1:
Input: [1, 1, 0, 1, 0]
Output: 4
Solution: Flip the 0 at index 2 to 1.

Example 2:
Input: [1, 0, 0, 1, 0]
Output: 2
Solution: Flip any of the 0 elements.

Example 3:
Input: [0, 0, 0, 0, 0]
Output: 1
Solution: Flip any of the 0 elements.

Example 4:
Input: [1, 1, 1, 1, 1]
Output: 5
No flip required.

Solution: Sliding Window Approach

To solve this problem efficiently, employ the sliding window technique. Start by initializing the left and right pointers to 0, and set the flipsCount to 0. Additionally, initialize the max variable to 0, which will keep track of the maximum length of the contiguous ones sequence.

Move the right pointer towards the right until encountering a 1. Upon encountering a 0, check the flipsCount. If flipsCount is 0, set flipsCount to 1 (considering the flip from 0 to 1), and continue moving the right pointer. If the element is 0 and flipsCount is already 1, it's time to move the left pointer.

Advance the left pointer until reaching a 0, and then reset flipsCount to 0. Continuously compare max with the current window size (right - left), updating max if necessary (max = Math.max(max, (right - left))).

By following this sliding window approach, you can efficiently determine the length of the longest contiguous sequence of ones with the allowance of a single flip

Time Complexity: O(N)

Output: 

Input: [1, 1, 0, 0, 1, 1, 1, 0, 1] Longest contiguous 1's with one flip allowed: 5

Related Problems: