1004. Max Consecutive Ones III
Max Consecutive Ones III (LeetCode 1004) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
How to solve Max Consecutive Ones III
Max Consecutive Ones III is a Variable Size Sliding Window problem, part of Sliding Window. Master variable-size sliding window for condition-based problems like longest substring without repeating characters.
Work towards the solution in these steps:
- One thing's for sure, we will only flip a zero if it extends an existing window of 1s. Otherwise, there's no point in doing it, right? Think Sliding Window!
- Since we know this problem can be solved using the sliding window construct, we might as well focus in that direction for hints. Basically, in a given window, we can never have > K zeros, right?
- We don't have a fixed size window in this case. The window size can grow and shrink depending upon the number of zeros we have (we don't actually have to flip the zeros here!).
The reference solution runs in O(n) time and O(1) space.
The Max Consecutive Ones III solution and editorial walks through the full approach with reference code.
Problem statement
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 1:
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] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Example 2:
Input: nums = [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.
Constraints:
- 1 <= nums.length <= 105
- nums[i] is either 0 or 1.
- 0 <= k <= nums.length
Topics and companies
Topics: Array, Binary Search, Sliding Window, Prefix Sum.
Reported in interviews at Facebook, Coupang, HBO.
How to practise Max Consecutive Ones III on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Max Consecutive Ones III in the code editor, or read the Max Consecutive Ones III editorial for a worked solution with its approach and complexity analysis.
Where Max Consecutive Ones III sits in the DSA pattern sheet
Problems related to Max Consecutive Ones III
Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:
- Contains Duplicate II — Easy, same subpattern
- Continuous Subarrays — Medium, same subpattern
- Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
- Frequency of the Most Frequent Element — Medium, same subpattern
- Fruit Into Baskets — Medium, same subpattern
- Jump Game VII — Medium, same subpattern
Max Consecutive Ones III FAQ
What is the LeetCode number of Max Consecutive Ones III?
Max Consecutive Ones III is LeetCode problem 1004, rated Medium.
What pattern is used to solve Max Consecutive Ones III?
Max Consecutive Ones III is a Variable Size Sliding Window problem. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
What is the time complexity of Max Consecutive Ones III?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Max Consecutive Ones III?
Max Consecutive Ones III has been reported in interviews at Facebook, Coupang, HBO.