Grokking the Coding Interview: Patterns for Coding Questions
Vote

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

.....

.....

.....

Like the course? Get enrolled and start learning!
Dave Wyatt

Dave Wyatt

· 2 months ago

Similar to the previous problem, an alternative way of expressing the logic of how the window only ever expands (we never bother checking for something lower than maxLen anyway):

type Solution struct{}

func (s Solution) findLength(arr []int, k int) int {
    maxLen := 0
    start := 0
    onesCount := 0
    maxOnesCount := 0

    for end := range arr {
        onesCount += arr[end]
        if onesCount > maxOnesCount {
            maxOnesCount = onesCount
            maxLen++
        } else if k > 0 {
            k--
            maxLen++
        } else {
            onesCount -= arr[start]
            start++
        }
    }
    return maxLen
}
Show 1 reply
L

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.

R

Roberto Pantoja

· 3 years ago

Instead of keeping track of the 1s, it might be more intuitive to follow the zeros.

Here's one way to do this.

static int findLength(const vector<int> &arr, int k)
    {
      int maxLength = 0, start = 0, tempK = 0;
      
      for(int end = 0; end < arr.size(); end++){
        if(arr[end] == 0)
          tempK++;

        // If there are too many zeros, increment start
        while(tempK > k){
          if(arr[start++] == 0)
            tempK --;
        }

        maxLength = max(maxLength, end - start + 1);
      }
      return maxLength;
    }

Anyone else approach the problem like this?

Show 2 replies
A

Anthony DiFede

· 4 years ago

Not sure if my solution is O(N) or O(N^2) with the inner while loop. I thought from the perspective of moving the window until there were only a max of k zeros in it. Image

A

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

P

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.

C

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.

Image

M

Max

· 4 years ago

keep track of the count of 0s Image

R

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?

Show 2 replies
P

Perry Robinson

· 5 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.

Show 1 reply

Reading Progress

0%

Vote for new content