Sliding window

Question 1

Max Consecutive Ones III
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.

Answer 1

’’’
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
l,r = 0,0
num_zeros = 0
window = 0
for r in range(len(nums)):
if nums[r] == 0:
num_zeros +=1
if num_zeros > k:
while num_zeros > k:
if nums[l] == 0:
num_zeros-=1
l+=1

        window = max(window, r-l+1)
    return window

’’’

1. l,r = 0,0 . right expands the window.
2. if num==0, then increment zero_count.
3. If zero_count > k, then slide left pointer, duing which if num[left] == 0, then decrement zero_count
4. Through this whole time keep track of max window length

Question 2

Fruit Into Baskets
You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.

** Basically find the longest window where there are only 2 types of numbers/fruits are present **

Example 1:

Input: fruits = [1,2,1]
Output: 3
Explanation: We can pick from all 3 trees.
Example 2:

Input: fruits = [0,1,2,2]
Output: 3
Explanation: We can pick from trees [1,2,2].
If we had started at the first tree, we would only pick from trees [0,1].
Example 3:

Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: We can pick from trees [2,3,2,2].
If we had started at the first tree, we would only pick from trees [1,2].

Answer 2

’’’
from collections import defaultdict
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
l,r = 0,0
window = 0
fruit_freq = defaultdict(int)
for r in range(len(fruits)):
fruit_freq[fruits[r]]+=1
if len(fruit_freq)>2:
while len(fruit_freq)>2:
fruit_freq[fruits[l]]-=1
if fruit_freq[fruits[l]] == 0:
del fruit_freq[fruits[l]]
l+=1

        window = max(window,r-l+1)
    return window ''' 1. l,r = 0,0. we keep a dictionary to keep track of frequency of each type of fruit 2. as r goes through it populates this dict. If len(dict) > 2 , as 2 is the max type of fruits. Then while len(dict) > 2, we slide the left pointer and decrement the frequency count of fruit[left] , if it becomes 0 then delete it 3. In the mean time keep the track of the window size.