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:
1
2
3
4
5
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:
1
2
3
4
5
Input:
nums = [1,1,1]
Output:
2
Explanation: You must delete one element.
We want the longest subarray of 1’s after deleting one element. By using a sliding window, we can keep at most one zero in the window (which represents the deleted element). We expand the window to the right, and if there are more than one zero, we shrink the window from the left until there is at most one zero. The answer is the largest window size minus one (since we must delete one element).
classSolution {
public:int longestSubarray(vector<int>& nums) {
int ans =0, k =1, s =0, numDeletes =0;
for (int e =0; e < nums.size(); ++e) {
if (nums[e] ==0) numDeletes++;
while (numDeletes > k) {
if (nums[s] ==0) numDeletes--;
s++;
}
ans = max(ans, e - s);
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
funclongestSubarray(nums []int) int {
ans, k, s, numDeletes:=0, 1, 0, 0fore:=0; e < len(nums); e++ {
ifnums[e] ==0 {
numDeletes++ }
fornumDeletes > k {
ifnums[s] ==0 {
numDeletes-- }
s++ }
ife-s > ans {
ans = e-s }
}
returnans}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution {
publicintlongestSubarray(int[] nums) {
int ans = 0, k = 1, s = 0, numDeletes = 0;
for (int e = 0; e < nums.length; e++) {
if (nums[e]== 0) numDeletes++;
while (numDeletes > k) {
if (nums[s]== 0) numDeletes--;
s++;
}
ans = Math.max(ans, e - s);
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution {
funlongestSubarray(nums: IntArray): Int {
var ans = 0var k = 1var s = 0var numDeletes = 0for (e in nums.indices) {
if (nums[e] ==0) numDeletes++while (numDeletes > k) {
if (nums[s] ==0) numDeletes-- s++ }
ans = maxOf(ans, e - s)
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution:
deflongestSubarray(self, nums: list[int]) -> int:
ans =0 k =1 s =0 numDeletes =0for e in range(len(nums)):
if nums[e] ==0:
numDeletes +=1while numDeletes > k:
if nums[s] ==0:
numDeletes -=1 s +=1 ans = max(ans, e - s)
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
impl Solution {
pubfnlongest_subarray(nums: Vec<i32>) -> i32 {
let (mut ans, k, mut s, mut num_deletes) = (0, 1, 0, 0);
for e in0..nums.len() {
if nums[e] ==0 { num_deletes +=1; }
while num_deletes > k {
if nums[s] ==0 { num_deletes -=1; }
s +=1;
}
ans = ans.max(e - s);
}
ans asi32 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution {
longestSubarray(nums: number[]):number {
letans=0, k=1, s=0, numDeletes=0;
for (lete=0; e<nums.length; e++) {
if (nums[e] ===0) numDeletes++;
while (numDeletes>k) {
if (nums[s] ===0) numDeletes--;
s++;
}
ans= Math.max(ans, e-s);
}
returnans;
}
}
Instead of using a sliding window, we can keep track of the number of consecutive 1s before and after each zero. For every zero, the sum of the number of 1s before and after it gives a candidate answer. If the array contains only 1s, we must delete one element, so the answer is n - 1.
funclongestSubarray(nums []int) int {
prevCnt, cnt, ans:=0, 0, 0n:= len(nums)
fori:=0; i < n; i++ {
ifnums[i] ==1 {
cnt++ } else {
ifcnt+prevCnt > ans {
ans = cnt+prevCnt }
prevCnt = cntcnt = 0 }
}
ifcnt+prevCnt > ans {
ans = cnt+prevCnt }
ifans==n {
returnans-1 }
returnans}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution {
publicintlongestSubarray(int[] nums) {
int prevCnt = 0, cnt = 0, ans = 0, n = nums.length;
for (int i = 0; i < n; i++) {
if (nums[i]== 1) {
cnt++;
} else {
ans = Math.max(ans, cnt + prevCnt);
prevCnt = cnt;
cnt = 0;
}
}
ans = Math.max(ans, cnt + prevCnt);
return ans == n ? ans - 1 : ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classSolution {
funlongestSubarray(nums: IntArray): Int {
var prevCnt = 0var cnt = 0var ans = 0val n = nums.size
for (i in nums.indices) {
if (nums[i] ==1) {
cnt++ } else {
ans = maxOf(ans, cnt + prevCnt)
prevCnt = cnt
cnt = 0 }
}
ans = maxOf(ans, cnt + prevCnt)
returnif (ans == n) ans - 1else ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution:
deflongestSubarray(self, nums: list[int]) -> int:
prev_cnt =0 cnt =0 ans =0 n = len(nums)
for v in nums:
if v ==1:
cnt +=1else:
ans = max(ans, cnt + prev_cnt)
prev_cnt = cnt
cnt =0 ans = max(ans, cnt + prev_cnt)
return ans -1if ans == n else ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
impl Solution {
pubfnlongest_subarray(nums: Vec<i32>) -> i32 {
let (mut prev_cnt, mut cnt, mut ans) = (0, 0, 0);
let n = nums.len();
for&v in&nums {
if v ==1 {
cnt +=1;
} else {
ans = ans.max(cnt + prev_cnt);
prev_cnt = cnt;
cnt =0;
}
}
ans = ans.max(cnt + prev_cnt);
if ans == n { (ans -1) asi32 } else { ans asi32 }
}
}