Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1004.html
Level
Medium
Description
Given an array A
of 0s and 1s, we may change up to K
values from 0 to 1.
Return the length of the longest (contiguous) subarray that contains only 1s.
Example 1:
Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation:
[1,1,1,0,0,++1++,++1++,++1++,++1++,++1++,++1++]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Example 2:
Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation:
[0,0,++1++,++1++,++1++,++1++,++1++,++1++,++1++,++1++,++1++,++1++,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Note:
1 <= A.length <= 20000
0 <= K <= A.length
A[i]
is0
or1
Solution
Loop over the array and store the start index of the subarray and the number of zeros in the subarray.
Initially, the start index start
is 0, and the number of zeros zerosCount
is 0. For each index i
from 0 to A.length - 1
, if A[i] == 0
, then increase zerosCount
by 1. As long as zerosCount <= K
, all zeros met so far can be changed to ones. If at one step zerosCount > K
, then move start
forward until the number of zeros in the subarray (from index start
to index i
) is not more than K
. At each index i
, update the max consecutive ones using i - start + 1
. Finally, return the max consecutive ones.
Code
-
public class Max_Consecutive_Ones_III { class Solution { public int longestOnes(int[] nums, int k) { int res = 0, zero = 0, left = 0; for (int right = 0; right < nums.length; ++right) { if (nums[right] == 0) ++zero; while (zero > k) { if (nums[left++] == 0) --zero; } res = Math.max(res, right - left + 1); } return res; } } } ############ class Solution { public int longestOnes(int[] nums, int k) { int l = 0, r = 0; while (r < nums.length) { if (nums[r++] == 0) { --k; } if (k < 0 && nums[l++] == 0) { ++k; } } return r - l; } }
-
// OJ: https://leetcode.com/problems/max-consecutive-ones-iii/ // Time: O(N) // Space: O(1) class Solution { public: int longestOnes(vector<int>& A, int k) { int i = 0, j = 0, cnt = 0, N = A.size(), ans = 0; while (j < N) { cnt += A[j++] == 0; while (cnt > k) cnt -= A[i++] == 0; ans = max(ans, j - i); } return ans; } };
-
class Solution: def longestOnes(self, nums: List[int], k: int) -> int: res, zero, left = 0, 0, 0 for right in range(len(nums)): if nums[right] == 0: zero += 1 while zero > k: if nums[left] == 0: zero -= 1 left += 1 res = max(res, right - left + 1) return res class Solution_followup: def findMaxConsecutiveOnes(self, nums: List[int]) -> int: res, left, k = 0, 0, 1 q = deque() for right in range(len(nums)): if nums[right] == 0: q.append(right) if len(q) > k: left = q.popleft() + 1 res = max(res, right - left + 1) # max-check every for iteration return res class Solution: def longestOnes(self, nums: List[int], k: int) -> int: l = r = -1 while r < len(nums) - 1: r += 1 if nums[r] == 0: k -= 1 if k < 0: l += 1 if nums[l] == 0: k += 1 return r - l ############ # 1004. Max Consecutive Ones III # https://leetcode.com/problems/max-consecutive-ones-iii/ class Solution: def longestOnes(self, nums: List[int], k: int) -> int: n = len(nums) i = 0 for j in range(n): if nums[j] == 0: k -= 1 if k < 0: if nums[i] == 0: k += 1 i += 1 return j - i + 1
-
func longestOnes(nums []int, k int) int { l, r := -1, -1 for r < len(nums)-1 { r++ if nums[r] == 0 { k-- } if k < 0 { l++ if nums[l] == 0 { k++ } } } return r - l }
-
function longestOnes(nums: number[], k: number): number { const n = nums.length; let l = 0; for (const num of nums) { if (num === 0) { k--; } if (k < 0 && nums[l++] === 0) { k++; } } return n - l; }
-
impl Solution { pub fn longest_ones(nums: Vec<i32>, mut k: i32) -> i32 { let n = nums.len(); let mut l = 0; for num in nums.iter() { if num == &0 { k -= 1; } if k < 0 { if nums[l] == 0 { k += 1; } l += 1; } } (n - l) as i32 } }