LeetCode Challenge #1493. Longest Subarray of 1's After Deleting One Element

Question 17 of 75 - LeetCode Weekly Challenge

LeetCode Challenge #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⁵
nums[i] is either 0 or 1.

Video Solution

C++ Solution

				
					class Solution {
public:

int longestSubarray(vector<int>& nums) {

        // Initialize variables: midZero is the index of the previous zero, i and j are pointers, ans is the final answer

        int midZero = -1;  // Initialize to -1 as there is no previous zero initially
        int i = 0;         // Start pointer
        int j = 0;         // End pointer
        int ans = 0;       // Variable to store the final result
        int n = nums.size(); // Size of the input array

        // Iterate through the array using the end pointer (j)
        while (j < n) {

            // If the current element at the end pointer is 0
            if (nums[j] == 0) {
                // Update the answer with the length of the current subarray (excluding the 0)
                ans = max(ans, j - i - 1);

                // Move the start pointer (i) to the index after the previous zero (midZero + 1)
                i = midZero + 1;

                // Update midZero to the current index (j)
                midZero = j;
            }

            // Move the end pointer to the next element
            j++;
        }

        // Update the answer one last time after reaching the end of the array
        ans = max(ans, j - i - 1);

        // Return the final result
        return ans;
    }
};

Code Explanation

In this program, the goal is to find the length of the longest subarray in the given vector ‘nums’ such that the subarray can be obtained by removing at most one zero. This solution includes a sliding window approach to efficiently explore the array.

Let’s see the step-by-step approach to the problem:

We have initialised ( midZero = -1 ) which indicates the position of the most recent zero encountered in the array.

Similarly ‘i’ and ‘j’ are also initialised with 0, representing the start and end of the current subarray respectively.
‘Ans’ is set to 0, which will eventually store the length of the longest subarray. Here, ‘i’ and ‘j’ are defining the Sliding window boundaries.

Then we used a ‘while’ loop that iterates through the array and continues until the ‘j’ pointer reaches the end of the array (‘n’).

Inside the loop, if the element at the current position ‘j’ is equal to 0 . this signifies the possibility of removing one zero to extend the subarray.

If it does, it updates the answer (‘ans’) by taking the maximum between the current answer and the length of length of the subarray from the previous zero (‘ j-i-1 ‘).

After this the window is now adjusted :

‘i’ is positioned after the most recent zero ( ‘midzero+1 ‘)
‘j’ is positioned to update ‘midzero’.

After the loop ends there’s a possibility that ‘j’ didn’t get any zero. So, we will again do the final updation by considering the length of the subarray until the end of the array (‘j – i – 1’).

The function returns the final value of ‘ans’, representing the length of the longest subarray that can be obtained by removing at most one zero.

Summary:- This solution maintains a sliding window and considers the impact of removing at most one zero to maximise the length of the subarray. The time complexity is O( n ) , where n is the length of the input array.

Question 17 of 75 - LeetCode Weekly Challenge