sliding window Flashcards
maximum average subarray
code
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
# Initialize currSum and maxSum to the sum of the initial k elements
currSum = maxSum = sum(nums[:k])
# Start the loop from the kth element
# Iterate until you reach the end
for i in range(k, len(nums)):
# Subtract the left element of the window
# Add the right element of the window
currSum += nums[i] - nums[i - k]
# Update the max
maxSum = max(maxSum, currSum)
# Since the problem requires average, we return the average
return maxSum / kmaximum average subarray
theory
Instead of creating a cumulative sum array first, and then traversing over it to determine the required sum, we can simply traverse over nums just once, and on the go keep on determining the sums possible for the subarrays of length k. To understand the idea, assume that we already know the sum of elements from index i to index i+k, say it is x.
Now, to determine the sum of elements from the index i+1 to the index i+k+1, all we need to do is to subtract the element nums[i] from x and to add the element nums[i+k+1] to x. We can carry out our process based on this idea and determine the maximum possible average.
maximum number of vowels in a substring of given length
theory
Initial Vowel Count: We first calculate the number of vowels in the initial window of size k (from index 0 to k-1). This gives us the starting point for the sliding window.
Sliding the Window:
For each position of the window, check the character that is leaving the window (on the left) and the one entering the window (on the right). If the character leaving is a vowel, decrement the vowel count; if the character entering is a vowel, increment the vowel count.
Keep track of the maximum vowel count as the window slides from the start to the end of the string.
Edge Case: If the string s has a length less than k, the function should handle that case as invalid input (though this isn’t required here, as per the problem constraints).
maximum number of vowels in a substring of given length
code
def maxVowels(self, s: str, k: int) -> int:
vowels = set('aeiou')
left = 1
right = k
count = 0
# Count the number of vowels in the first window of size k
for i in range(k):
if s[i] in vowels:
count += 1
# Initialize the maximum answer to the count in the first window
ans = count
# Slide the window across the string
while right < len(s):
# Remove the effect of the character that is sliding out (left-1)
if s[left - 1] in vowels:
count -= 1
# Add the effect of the character that is sliding in (right)
if s[right] in vowels:
count += 1
# Update the answer if the current window has more vowels
ans = max(ans, count)
# Move the window
left += 1
right += 1
return ansmax consecutive ones iii
algorithm
Initialize two pointers. The two pointers help us to mark the left and right end of the window/subarray with contiguous 1’s.
left = 0, right = 0, window_size = 0
We use the right pointer to expand the window until the window/subarray is desirable. i.e. number of 0’s in the window are in the allowed range of [0, k].
Once we have a window which has more than the allowed number of 0’s, we can move the left pointer ahead one by one until we encounter 0 on the left too. This step ensures we are throwing out the extra zero.
max consecutive ones iii
code
def longestOnes(nums: List[int], k: int) -> int:
left = 0
for right in range(len(nums)):
# If we included a zero in the window we reduce the value of k.
# Since k is the maximum zeros allowed in a window.
k -= 1 - nums[right]
# A negative k denotes we have consumed all allowed flips and window has
# more than allowed zeros, thus increment left pointer by 1 to keep the window size same.
if k < 0:
# If the left element to be thrown out is zero we increase k.
k += 1 - nums[left]
left += 1
return right - left + 1longest subarray of 1s after deleting one element
theory
We have a binary array nums with size N; we need to delete exactly one element from it and then return the longest subarray having only 1. Since we need to maximize the count of 1 in the subarray, we should not delete a 1, except in the case when the array has all elements as 1 (then we don’t have a choice).
Although we need a subarray with all elements as 1, we can afford to have one 0 as we can delete it. We will keep a window and keep adding elements as long as the count of 0s in it doesn’t exceed one. Once the number of 0s exceeds one, we will shrink the window from the left side till the count of 0 comes under the limit; then, we can compare the size of the current window with the longest subarray we have got so far.
This algorithm will cover the edge case with no zeroes, as in that case, the zeroCount will never exceed 1, and our window will cover the whole array. In the end, the difference between the first and last index would provide the array size minus 1, which is intended as we need to delete one element.
longest subarray of 1s after deleting one element
code
class Solution:
# def check(self)
def find(self,nums,guess):
start = 0
end = start + guess
s = sum(nums[start:end])
while end < len(nums):
l = end - start
if (l-s) <= 1:
return s
s-=nums[start]
start+=1
s+=nums[end]
end+=1
l = end - start
if (l-s) <= 1:
return s
return -1
def longestSubarray(self, nums: List[int]) -> int:
lo = 0
hi = len(nums)
ans = 0
while lo<=hi:
mid = (lo+hi)//2
possible = self.find(nums,mid)
if possible != -1:
ans = max(ans,mid-1)
lo=mid+1
else:
hi=mid-1
return ansmax consecutive ones: intuition
We can use a simple sliding window approach to solve this problem.
In any sliding window based problem we have two pointers. One right pointer whose job is to expand the current window and then we have the left pointer whose job is to contract a given window. At any point in time only one of these pointers move and the other one remains fixed.
The solution is pretty intuitive. We keep expanding the window by moving the right pointer. When the window has reached the limit of 0’s allowed, we contract (if possible) and save the longest window till now.
The answer is the longest desirable window.
