Longest Subarray of 1’s After Deleting One Element LeetCode Solution

Difficulty Level Medium
Frequently asked in YandexViews 4212

Problem Statement

Longest Subarray of 1’s After Deleting One Element LeetCode Solution – Given 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:

Test Case 1:

Input:

nums = [0, 1, 1, 0, 1, 1, 0, 1]

Output:

4

Explanation for Longest Subarray of 1’s After Deleting One Element:

We can delete the 0 at index 3 to get the longest sub-array containing only 1’s. So the output is 4.

Longest Subarray of 1's After Deleting One Element LeetCode Solution

Approach

Idea:

We can iterate the array and when we find 0, we can calculate no of 1s until we get another 0. After that, we can again check for no of 1s from the previous 0. But here we are doing repetitive work. So we can optimize it by storing no of 1s after we encounter 0 so that we won’t have to count it again.

When we encounter a 0, there are 2 situations. Either it is the first 0 in the window or we might have encountered another 0 before. If it is the first 0, we need this current count but if it’s the second 0, we need the count of no of 1s before the first 0  to get the length of the total subarray. So every time we encounter 0,  we can store the currentCount into another variable previousCount, and then set current count to 0. If all the elements in the array are 1,  we can return array size – 1.

Longest Subarray of 1's After Deleting One Element LeetCode Solution

Code

Java Program for Longest Subarray of 1’s After Deleting One Element

class Solution {
    public int longestSubarray(int[] nums) {
        int previousCount = 0, currentCount = 0, maxCount = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) 
              currentCount++;
            else {
                maxCount = Math.max(maxCount, currentCount + previousCount);
                previousCount = currentCount;
                currentCount = 0;
            }
        }
        maxCount = Math.max(maxCount, currentCount + previousCount);
        return maxCount == nums.length ? maxCount - 1 : maxCount;
    }
}

C++ Program for Longest Subarray of 1’s After Deleting One Element

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int previousCount = 0, currentCount = 0, maxCount = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 1) 
              currentCount++;
            else {
                maxCount = max(maxCount, currentCount + previousCount);
                previousCount = currentCount;
                currentCount = 0;
            }
        }
        maxCount = max(maxCount, currentCount + previousCount);
        return maxCount == nums.size() ? maxCount - 1 : maxCount;
    }
};

Complexity Analysis for Longest Subarray of 1’s After Deleting One Element LeetCode Solution

Time Complexity

Here we are traversing the array only once. So time complexity is O(n), where n is the size of the array.

Space Complexity

We are just using constant space. So space complexity is O(1).

Reference: https://en.wiktionary.org/wiki/subarray

 

 

 

 

 

Translate »