0% completed
Solution: Longest Subarray with Ones after Replacement
Problem Statement
Given an array containing 0s and 1s, if you are allowed to replace no more than ‘k’ 0s with 1s, find the length of the longest contiguous subarray having all 1s.
Example 1:
Input: Array=[0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1], k=2
Output: 6
Explanation: Replace the '0' at index 5 and 8 to have the longest contiguous subarray of 1s having length 6.
Example 2:
Input: Array=[0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], k=3
Output: 9
.....
.....
.....
Max
· 4 years ago
keep track of the count of 0s
Mikhail Putilov
· 4 years ago
maxOnesCount does not keep track of the maximum number of repeating 1s in the current window
It is just a number of 1s in the current window.
lejafilip
· 2 years ago
Especially while we compare it to previous one. It's just applying pattern like in medium problems. Consider to change it to medium.
SeungJin Kim
· 4 years ago
It's more intuitive for me to keep track of the count of 0s instead. The condition then will be 'if zero count > k:'
Pete Stenger
· 4 years ago
For the previous problem, we kept track of the maximum count of a single letter to make sure the window size never dips below the maximum count of a letter, and are needlessly evaluating solutions.
It appears the solution for this problem doesn't have this optimization, is there a reason why?
It looks as if 'maxOnesCount' is really 'onesInWindow', and the optimization to skip these unneeded solutions is missing.
Perry Robinson
· 4 years ago
I keep going through these sliding window problems and can't really seem to spot a pattern other than it's a sliding window pattern. How do you know if you will need to use an array or a hashmap in your solution? It would be more helpful if there was boilerplate template for the sliding window pattern that you could always start with and adjust to fit the problem.
Richard Yuan
· 4 years ago
Is there a specific reason why we didn't decrement max_repeat_letter_count in the previous problem, but we decrement max_ones_count in this problem? Don't they represent the same thing in their respective problems?
Alex
· 4 years ago
Shouldn't we need to use a while loop to see if the window has become invalid rather than an if statement? Consider the situation in which arr[windowStart] = 1 when we enter the if statement. In that case, we'll decrement maxOnesCount and also increment windowStart. This means that when we leave the if statement, we will still have an invalid window (i.e. windowEnd - windowStart + 1 - maxOnesCount will still be greater than k).
Austin McDaniel
· 4 years ago
from collections import Counter class Solution: def longestOnes(self, nums: List[int], k: int) -> int:
max_ones = 0 w_start = 0 bit_count = Counter() bit_count[0] = 0
for w_end in range(len(nums)):
bit_count[nums[w_end]] += 1
if w_end - w_start + 1 - bit_count[1] > k: bit_count[nums[w_start]] -= 1 w_start +=1 else: max_ones = max(w_end - w_start + 1, max_ones)
return max_ones
I believe this is a more intuitive solution. The idea is that we're seeing the difference between the window size and the thing we are trying to maximize. In this case we are trying to maximize 1s, and that difference must be bigger than the allowed amount of replacements otherwise we have too many replacements and must decrement out window size. The only difference between this problem and the letter problem i
Clodoaldo Favaro
· 4 years ago
I got a similar solution to Max's. The only difference is that I kept counters for 0s and 1s in an object.
