Longest Subarray of Ones After Deleting One Element [Medium]
Sanjeev SharmaAdvertisement
Problem Statement
Given a binary array nums, delete exactly one element and return the length of the longest non-empty subarray of 1s remaining.
Input: [1,1,0,1] → Output: 3
Input: [0,1,1,1,0,1,1,0,1] → Output: 5
Intuition
Allow at most 1 zero in window. Window size - 1 = result (the deleted element).
Solutions
C++
int longestSubarray(vector<int>& nums) {
int left=0, zeros=0, ans=0;
for(int r=0;r<nums.size();r++){
if(!nums[r]) zeros++;
while(zeros>1){if(!nums[left++])zeros--;}
ans=max(ans,r-left); // -1 for deleted element
}
return ans;
}
Python
def longestSubarray(nums: list[int]) -> int:
left = zeros = ans = 0
for right, val in enumerate(nums):
if val == 0: zeros += 1
while zeros > 1:
if nums[left] == 0: zeros -= 1
left += 1
ans = max(ans, right - left)
return ans
Complexity
- Time: O(n), Space: O(1)
Advertisement
