Longest Subarray of 1s After Deleting One Element [Medium] — Sliding Window
Sanjeev SharmaAdvertisement
Problem Statement
Given a binary array nums, delete one element and return the length of the longest non-empty subarray of 1s in the result.
Input: [1,1,0,1] → Output: 3
Input: [0,1,1,1,0,1,1,0,1] → Output: 5
Intuition
Sliding window that allows at most 1 zero. But since we must delete exactly one element, the answer = window_length - 1 (the deleted element slot).
Solutions
C++
int longestSubarray(vector<int>& nums) {
int left=0, zeros=0, ans=0;
for (int right=0;right<nums.size();right++) {
if(!nums[right]) zeros++;
while(zeros>1) { if(!nums[left]) zeros--; left++; }
ans=max(ans,right-left); // window-1 (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) # window size - 1
return ans
JavaScript
var longestSubarray = function(nums) {
let left=0, zeros=0, ans=0;
for(let right=0;right<nums.length;right++){
if(!nums[right]) zeros++;
while(zeros>1){if(!nums[left])zeros--;left++;}
ans=Math.max(ans,right-left);
}
return ans;
};
Complexity
- Time: O(n)
- Space: O(1)
Advertisement
