Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1493.html
1493. Longest Subarray of 1’s After Deleting One Element (Medium)
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.
Example 4:
Input: nums = [1,1,0,0,1,1,1,0,1] Output: 4
Example 5:
Input: nums = [0,0,0] Output: 0
Constraints:
1 <= nums.length <= 10^5
nums[i]
is either0
or1
.
Related Topics:
Array
Solution 1.
prev2
and prev
are the indexes of the non-one values we’ve seen most recently during scanning.
prev2 prev i
0 1 1 1 0 1 1 1 0
If the array only contains 1, then return N - 1
.
Otherwise, the answer is the maximum of i - prev2 - 2
.
// OJ: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int longestSubarray(vector<int>& A) {
int N = A.size(), prev2 = -1, prev = -1, ans = 0;
for (int i = 0; i <= N; ++i) {
if (i < N && A[i] == 1) continue;
if (i == N && prev == -1) return N - 1;
if (prev != -1) ans = max(ans, i - prev2 - 2);
prev2 = prev;
prev = i;
}
return ans;
}
};
Solution 2. Sliding Window
Sliding window [i, j)
with at most 2
zeros.
- Keep extending the right edge until the window becomes invalid, i.e. more than one zero, or can’t be extended any more.
- Now
cnt
can be either0
,1
or2
. The corresponding size after deleting one element isj - i - max(cnt, 1)
. - Then we shrink the left edge until
cnt
becomes valid, i.e.cnt <= 1
. - Back to step 1 until the window reaches the end.
// OJ: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int longestSubarray(vector<int>& A) {
int i = 0, j = 0, N = A.size(), cnt = 0, ans = 0;
while (j < N) {
while (j < N && cnt <= 1) cnt += A[j++] == 0;
ans = max(ans, j - i - max(cnt, 1));
while (cnt > 1) cnt -= A[i++] == 0;
}
return ans;
}
};
Solution 3. Sliding Window
Sliding window [i, j)
with at most 1
zero.
- Keep extending the right edge until it reaches the end or one more extension will include 2 zeros.
j - i - 1
is the corresponding answer for this window.- Shrink the left edge until
cnt == 0
. - Back to step 1 until the window reaches the end.
// OJ: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int longestSubarray(vector<int>& A) {
int i = 0, j = 0, N = A.size(), cnt = 0, ans = 0;
while (j < N) {
while (j < N && cnt + (A[j] == 0) <= 1) cnt += A[j++] == 0;
ans = max(ans, j - i - 1);
while (cnt == 1) cnt -= A[i++] == 0;
}
return ans;
}
};
Solution 4. Sliding Window
Sliding window [i, j]
with at most 1
zero.
- Keep extending the right edge.
- Once the
cnt > 1
, shrink the left edge. - The size for this window with one deletion is
j - i
. - Back to step 1 until it reaches the end.
This solution is simpler than the previous one because we don’t need to think about when to stop the extension of the right edge.
// OJ: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int longestSubarray(vector<int>& A) {
int i = 0, j = 0, N = A.size(), cnt = 0, ans = 0;
for (; j < N; ++j) {
cnt += A[j] == 0;
while (cnt > 1) cnt -= A[i++] == 0;
ans = max(ans, j - i);
}
return ans;
}
};
Solution 5. Sliding Window
Sliding window [i - ans + 1, i]
with at most 1
zero that never shrinks.
// OJ: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int longestSubarray(vector<int>& A) {
int N = A.size(), cnt = 0, ans = 0;
for (int i = 0; i < N; ++i) {
cnt += A[i] == 0;
if (cnt > 1) cnt -= A[i - ans] == 0;
else ++ans;
}
return ans - 1;
}
};
Sliding window [i, j]
with at most 1
zero taht never shrinks.
// OJ: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int longestSubarray(vector<int>& A) {
int i = 0, j = 0, N = A.size(), cnt = 0;
for (; j < N; ++j) {
cnt += A[j] == 0;
if (cnt > 1) cnt -= A[i++] == 0;
}
return j - i - 1;
}
};
-
class Solution { public int longestSubarray(int[] nums) { int length = nums.length; int index = 0; while (index < length && nums[index] == 0) index++; if (index == length) return 0; List<Integer> ones = new ArrayList<Integer>(); List<Integer> zeros = new ArrayList<Integer>(); int prev = 1; int count = 1; for (int i = index + 1; i < length; i++) { int num = nums[i]; if (num == prev) count++; else { if (prev == 1) ones.add(count); else zeros.add(count); prev = num; count = 1; } } if (prev == 1) ones.add(count); else zeros.add(count); if (index == 0 && zeros.size() == 0) return ones.get(0) - 1; int maxLength = ones.get(0); int size = ones.size(); for (int i = 1; i < size; i++) { int zero = zeros.get(i - 1); int prevOne = ones.get(i - 1); int one = ones.get(i); maxLength = Math.max(maxLength, one); if (zero == 1) maxLength = Math.max(maxLength, prevOne + one); } return maxLength; } } ############ class Solution { public int longestSubarray(int[] nums) { int n = nums.length; int[] left = new int[n]; int[] right = new int[n]; for (int i = 1; i < n; ++i) { if (nums[i - 1] == 1) { left[i] = left[i - 1] + 1; } } for (int i = n - 2; i >= 0; --i) { if (nums[i + 1] == 1) { right[i] = right[i + 1] + 1; } } int ans = 0; for (int i = 0; i < n; ++i) { ans = Math.max(ans, left[i] + right[i]); } return ans; } }
-
// OJ: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/ // Time: O(N) // Space: O(1) class Solution { public: int longestSubarray(vector<int>& A) { int N = A.size(), prev2 = -1, prev = -1, ans = 0; for (int i = 0; i <= N; ++i) { if (i < N && A[i] == 1) continue; if (i == N && prev == -1) return N - 1; if (prev != -1) ans = max(ans, i - prev2 - 2); prev2 = prev; prev = i; } return ans; } };
-
class Solution: def longestSubarray(self, nums: List[int]) -> int: n = len(nums) left = [0] * n right = [0] * n for i in range(1, n): if nums[i - 1] == 1: left[i] = left[i - 1] + 1 for i in range(n - 2, -1, -1): if nums[i + 1] == 1: right[i] = right[i + 1] + 1 return max(left[i] + right[i] for i in range(n))
-
func longestSubarray(nums []int) int { n := len(nums) left := make([]int, n) right := make([]int, n) for i := 1; i < n; i++ { if nums[i-1] == 1 { left[i] = left[i-1] + 1 } } for i := n - 2; i >= 0; i-- { if nums[i+1] == 1 { right[i] = right[i+1] + 1 } } ans := 0 for i := 0; i < n; i++ { ans = max(ans, left[i]+right[i]) } return ans } func max(a, b int) int { if a > b { return a } return b }