MediumNo. 1004
Max Consecutive Ones III — LeetCode 1004 Python Solution
- Pattern
- Sliding Window
- Topics
- Array, Binary Search, Prefix Sum, Sliding Window
- On a study list
- LeetCode 75
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.
Example
- Input
- nums = [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]
Python solution
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
l = cnt = 0
for x in nums:
cnt += x ^ 1
if cnt > k:
cnt -= nums[l] ^ 1
l += 1
return len(nums) - lComplexity
- Time
- O(n)where n is the length of the array
- Space · auxiliary
- O(1)
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1004. Max Consecutive Ones III is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0485 | Max Consecutive Ones | Easy |
| 0209 | Minimum Size Subarray Sum | Medium |
| 0713 | Subarray Product Less Than K | Medium |
| 0862 | Shortest Subarray with Sum at Least K | Hard |
| 2106 | Maximum Fruits Harvested After at Most K Steps | Hard |
| 2302 | Count Subarrays With Score Less Than K | Hard |
Frequently asked questions
- How hard is LeetCode 1004. Max Consecutive Ones III?
LeetCode 1004. Max Consecutive Ones III is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1004. Max Consecutive Ones III?
The Python solution on this page runs in O(n), where n is the length of the array.
- What is the space complexity of LeetCode 1004. Max Consecutive Ones III?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1004. Max Consecutive Ones III cover?
LeetCode 1004. Max Consecutive Ones III is tagged Array, Binary Search, Prefix Sum and Sliding Window on LeetCode.