Sliding Window
1. Subarrays
•
Subarray is a contiguous section of the array, all the elements must be adjacent to each other in the original array and in their original order.
◦
Subarrays of array [1,2,3,4] are
▪
[1], [2], [3], [4]
▪
[1,2], [2,3], [3,4]
▪
[1,2,3], [2,3,4]
▪
[1,2,3,4]
•
Subarray can be defined by two indices; left and right
•
Another name for subarray in this context is “window”
2. Sliding windows
When should we used sliding windows
1.
The problem wil either explicitly or implicitly define criteria that make a subarray ‘valid’.
There are 2 components regarding what makes a subarray valid:
•
A constraint metric : Contraint metric can be a some attribute of a subarray, it could be the sum, the number of unique elements, the frequency of a specific element, etc..
•
A numeric restriction on the constrain metric : This is what the constraint metric should be for a subarray to be considered valid.
If there’s a problem that declares a subarray is valid if it has a sum less than or equal to 10.
•
constraint metric : sum of the subarray
•
numeric restriction : ≤ 10
•
Subarray is considered valid if its constraint metric conforms to the numeric restriction
2.
The problem will ask you to find valid subarrays in some ways.
•
The most common task found is finding the best valid subarray.
•
The problem will define what makes a subarray better than another
3.
Examples of sliding widnow
•
Find the longest subarray with a sum less thatn or equal to k
•
Find the longest substring that has at most one “0”
Sliding window Algorithm
•
The main idea of using sliding window is considering only valid subarrays.
◦
Initial state of two variables that define current subarray is left = right = 0
◦
By incrementing right, we can expand the size of our “window”
◦
By incrementing left, we can reduce the size of our “window”
•
As we add and remove elements, we are ‘sliding’ our window along the input from left to right.
•
The size of the window constantly changes but it always slides along to the right, until we reach the end of the input.
Implementation
Example
Find the length of the longest subarray that has a sum less than or equal to k
nums = [3, 2, ,1, 3, 1, 1, 5], k = 5
•
constant numeric : sum of the window
def window(nums, k):
left, curr = 0, 0
answer = 0
for right in range(len(nums)):
curr += nums[right]
while curr > k:
curr -= nums[left]
left += 1
answer = max(answer, right-left+1)
Python
복사
•
we can leverage a variable curr for keeping track of the current sum.
◦
when adding a new element from the right ; curr += nums[right]
◦
when removing an element from the left; curr -= nums[left]
•
we have to shrink our window only if it becomes invalid
◦
by adding the condition curr ≤ k, we can check the validity of our window.
Time Efficiency of Sliding Window
•
There are total subarrays of an array that has a length of n
→ In terms of time complexity, any algorithm that looks every subarray will be at least
•
Sliding window guarantees a maximum of window iteration, resulting its total time complexity
◦
the right pointer can move times and the left pointer can move times
Example 1 : Binary String
•
You are given a binary string s (a string containing only "0" and "1"). You may choose up to one "0" and flip it to a "1". What is the length of the longest substring achievable that contains only "1"?
def binary(s):
left, curr, ans = 0, 0, 0
for right in range(len(s)):
if s[right]== '0':
curr += 1
while curr > 1:
if s[left] == '0':
curr -= 1
left += 1
ans = max(ans, right-left+1)
return ans
Python
복사
•
constraint metric : how many 0s in the substring
•
numeric restriction : ≤ 1
•
curr : current number of zeros in the window
