LeetCode //C - 1493. Longest Subarray of 1‘s After Deleting One Element

1493. Longest Subarray of 1’s After Deleting One Element

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1’s in the resulting array. Return 0 if there is no such subarray.
 

Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1’s.

Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1’s is [1,1,1,1,1].

Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Constraints:

• $1<=nums.length<=10^5$
• nums[i] is either 0 or 1.

From: LeetCode
Link: 1493. Longest Subarray of 1’s After Deleting One Element

Solution:

Ideas：

1. Keep track of the length of the current sequence of 1’s (curr_len).
2. Keep track of the length of the previous sequence of 1’s (prev_len).
3. When encountering a 0, update max_len if the sum of curr_len and prev_len plus 1 (for the current 0) is greater than max_len.
4. After encountering a 0, update prev_len to curr_len (since we can potentially delete this 0 to connect the previous and current sequences of 1’s) and reset curr_len.
5. After the loop, perform one last check to update max_len because the array might end with a sequence of 1’s.
6. Return max_len - 1 because we must delete one element. However, if the array contains only 1’s, the function should return numsSize - 1.

Code:

int longestSubarray(int* nums, int numsSize) {
   
    int max_len = 0;
    int curr_len = 0;
    int prev_len = 0;

    for (int i = 0; i < numsSize; i++) {
   
        if (nums[i] == 1) {
   
            curr_len++;
        } else {
   
            max_len = (prev_len + curr_len > max_len) ? prev_len + curr_len : max_len;
            prev_len = curr_len + 1; // Include the current 0 as it could be deleted
            curr_len = 0;
        }
    }

    max_len = (prev_len + curr_len > max_len) ? prev_len + curr_len : max_len;

    // Since we need to delete one element, subtract 1, except when the array is all 1s
    return (numsSize != curr_len) ? max_len - 1 : numsSize - 1;
}