This post is completed by 4 users

  • 2
 Add to List
Medium

547. Maximum Contiguous ones after one deletion

Given a binary array (only 0's and 1's). You need to find the length of longest contiguous 1's after deletion of one element from the array.

Examples: 
Let's consider a few examples to understand the concept better:

Example 1:
Input: [1, 1, 0, 1, 0]
Output: 3
Explanation: By deleting the 0 at index 2, we obtain the array [1, 1, 1, 0]. The longest contiguous sequence of 1's in this modified array has a length of 3.

Example 2:
Input: [1, 0, 0, 1, 0]
Output: 1
Explanation: After deleting any element, the longest contiguous sequence of 1's in the modified array will be 1.

Example 3:
Input: [0, 0, 0, 0, 0]
Output: 0
Explanation: Deleting any element will result in an array with all 0's, so the longest contiguous sequence of 1's will be 0.

Example 4:
Input: [1, 1, 1, 1, 1]
Output: 4
Explanation: After deleting any element, the entire array consists of 1's, so the longest contiguous sequence of 1's will be the length of the array minus 1.
Approach:


To find the length of the longest contiguous sequence of 1's after removing a single element, we can follow these steps:

  1. Identify all occurrences of contiguous 1's in the binary array. For example, given the array [1, 1, 0, 0, 1, 0, 1, 1, 1], the occurrences of contiguous 1's will be [2, 0, 1, 3]. Note that there are no 1's between the zeros [0, 0]. Store these occurrences in a list.
  2. Iterate through the list and find two consecutive numbers that sum up to the maximum value. In our example, the maximum sum would be 1 + 3 = 4.
  3. Handle edge cases: If all elements in the array are 1, return the length of the array minus 1. If all elements are 0, return 0, as there will be no contiguous 1's after deletion.

Utilizing the Sliding Window Technique: The sliding window technique can be applied to solve this problem efficiently. By maintaining two pointers that define the window's boundaries, we can slide the window through the array, keeping track of the maximum contiguous sequence of 1's. Please read - Maximum contiguous ones after one flip - sliding window

Time Complexity: O(N)

Output: 
Input: [1, 1, 0, 0, 1, 1, 1, 0, 1]
Longest contiguous 1's after one deletion: 4

Related Problems: