Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Longest Subarray with Ones after Replacement

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

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

A

Anonymous

· 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

Anonymous

· 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

Anonymous

· 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

A

Anonymous

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

A

Anonymous

· 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

A

Anonymous

· 4 years ago

keep track of the count of 0s Image

A

Anonymous

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

Anonymous

· 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
A

Anonymous

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

Show 1 reply

Reading Progress

0%

Vote for new content