Longest Subarray of 1's After Deleting One Element Solution
Longest Subarray of 1's After Deleting One Element solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Longest Subarray of 1's After Deleting One Element is a medium coding problem on arrays, dynamic programming and sliding window, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Sliding Window
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a binary array nums, you must delete exactly one element from it.
Return the size of the longest non-empty subarray of 1s in the resulting array. If no such subarray exists, return 0.
Example 1
Input: nums = [1,1,0,1]
Output: 3
Explanation: Deleting the 0 leaves [1,1,1].
Example 2
Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Example 3
Input: nums = [1,1,1]
Output: 2
Explanation: One element must be deleted even though the array is all 1s.
Constraints
1 <= nums.length <= 40nums[i] is either 0 or 1.
Hints for Longest Subarray of 1's After Deleting One Element
Hint 1
Slide a window that is allowed to contain at most one zero.
Hint 2
The answer for a window is its length minus one — the deleted element, whether it is the zero or a spare 1.
Hint 3
That
- 1is what makes the all-ones case come out right.
How to solve Longest Subarray of 1's After Deleting One Element
Slide a window containing at most one zero; the answer for a window is its length minus one, since exactly one element must be deleted.
Approach
- Expand
right; count zeros in the window. - While the window holds more than one zero, advance
left(decrementing the count when a zero leaves). - Update the best with
right - left(window length minus one).
Why it works
Deleting the single zero in a window leaves a run of length - 1 ones; if the window has no zero, deleting any one element still leaves length - 1. Every longest answer is contained in some such window.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- An all-ones array must return
n - 1, which the- 1handles without a special case.
Reference solution
Python
def longestSubarray(nums) -> int:
left = zeros = best = 0
for right, x in enumerate(nums):
if x == 0:
zeros += 1
while zeros > 1:
if nums[left] == 0:
zeros -= 1
left += 1
best = max(best, right - left)
return bestJava
public static int longestSubarray(int[] nums) {
int left = 0, zeros = 0, best = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0) zeros++;
while (zeros > 1) {
if (nums[left] == 0) zeros--;
left++;
}
best = Math.max(best, right - left);
}
return best;
}C++
int longestSubarray(vector<int>& nums) {
int left = 0, zeros = 0, best = 0;
for (int right = 0; right < (int) nums.size(); right++) {
if (nums[right] == 0) zeros++;
while (zeros > 1) {
if (nums[left] == 0) zeros--;
left++;
}
best = max(best, right - left);
}
return best;
}JavaScript
var longestSubarray = function(nums) {
let left = 0, zeros = 0, best = 0;
for (let right = 0; right < nums.length; right++) {
if (nums[right] === 0) zeros++;
while (zeros > 1) {
if (nums[left] === 0) zeros--;
left++;
}
const len = right - left;
if (len > best) best = len;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming