Sliding Window
Sliding windows enable naive quadratic+ algorithms to be more efficient, usually reducing the exponent, i.e. quadratic solutions often become linear, etc. They work by expanding & contracting a window as it slides across an array or string. Frequently, it is necessary to compute some quantity along the way in search of the maximum value.
Algorithm
Initialize l & r, the left & right edges of the sliding window, a hashmap|set|variant called window, for tracking the frequency|quantity needed to test for inclusion in the window, & max|etc, to track any quantity needing to be computed on the window. TODO: update this after experiencing more sliding window examples.
while r < n:
if a[r] meets the criteria for joining the sliding window:
add a[r] to the window by membership|calculation|variant
slide r right
update max|etc to track quantity computed on the window
else:
remove[a[l]] from the window
slide l right
update running quantity as needed
return max|etcProblems
- Maximum Length Subarray with at most K frequency
- Count Subarrays Where Max Element Appears at Least K Times
- Longest Substring Without Repeating Characters
- Minimum Size Subarray Sum
- Repeated DNA Sequences
- Shortest Subarray With OR at Least K II
- 3Sum
- 3Sum Smaller
- 3Sum Closest
Maximum Length Subarray with at most K frequency
Given an integer array & frequency k, return the maximum length subarray with no element of frequency greater than k.
Explore
k=1 k=0 k=1
1 2 3 4 1 5 1 2 3 4 1 5 1 2 3 4 3 5
1 2 3 4 max=0 1 2 3 4
2 3 4 1 5 4 3 5
max=5 max=4
- each time we move r, increment count & counts[a[i]] & check for new max length subarray.
- when moving l, decrement the count & counts[a[i]]
Python Solution
class Solution:
def maxSubarrayLength(self, nums: List[int], k: int) -> int:
a, n, count, max_sa, l, r, counts = nums, len(nums), 0, 0, 0, 0, Counter()
while r < n:
if counts[a[r]] < k:
counts[a[r]] += 1
count += 1
r += 1
max_sa = max(count, max_sa)
else:
counts[a[l]] -= 1
count -= 1
l += 1
return max_saComplexity Analysis
This particular sliding window requires at worst 2 passes through the input using O(n) time & O(n) space to keep track of what is in the window.
C++ Solution
TODO: c++ solution
Count Subarrays Where Max Element Appears at Least K Times
Given an array of integers & a positive integer k, return the number of subarrays which contain the maximum element of the input array at least k times.
Explore
k=2
1 0 0 1 1 0 0 1
s e 1
se 4
s e 4
s e 4
s e 5
s = 18
The idea is to count the number of valid subarrays ending at the ith index.
- Iterate through all i in the input array counting the valid subarrays at ending at i.
- Collapse from the left until the window is no longer valid.
- Add this index, l, to the number of valid subarrays → each valid subarray, (l,r), will have l valid subarrays to add to the total. Once l moves right of a valid subarray, l will be the correct addition due to zero indexing.
- Continue step #1.
Python Solution
class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
a, n, soln, l, r, kcount, smax = nums, len(nums), 0, 0, 0, 0, max(nums)
for r in range(n): # count subarrays ending at i -> r must try every i
if a[r] == smax: # same as while w/ a[r] meets always criteria
kcount += 1
while kcount == k: # kcount !> k -> k > 0
if a[l] == smax:
kcount -= 1
l += 1
soln += l
return solnComplexity Analysis
We traverse the input array linearly visiting each index at most twice with the edges of our window & keeping track of the count of subarrays & maximum values which is O(n) time & O(1) space.
Longest Substring Without Repeating Characters
Given a string, return the longest substring without repeating characters.
Explore
abcdefgabcd
12345677777
Python Solution
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
a, n, l, r, smax, window = a, len(s), 0, 0, 0, set()
while r < n:
if a[r] not in window:
window.add(a[r])
r += 1
smax = max(smax, r - l)
else:
window.remove(a[l])
l += 1
return smax
Find the Most Frequent Possible Integer With K Operations
Given an Array & K Increment Operations, find the integer with the highest possible frequency after K operations on the given array.
Explore
k = 5
9 2 3 4 5 6
2 3 4 5 6 9
2
2 3
2 3 4
3 4 5
4 5 6
6 9
- Sort the array from least to greatest given our operations can only increment & our need to consider distances between integers.
- Employ a sliding window over the input, considering r to be the target value after k increments at each step & keep track of the sum of the current window to calculate the # of operations needed to reach the target.
- Close the sliding window from the left until it is valid after k operations.
- Update the max valid window encountered.
- Goto #2.
Python Solution
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
a, n, l, r, rsum, maxw = nums, len(nums), 0, 0, 0, 0
a.sort()
while r < n:
target = a[r]
rsum += target
while target * (r - l + 1) - rsum > k:
rsum -= a[l]
l += 1
maxw = max(maxw, r - l + 1)
r += 1
return maxw
Minimum Size Subarray Sum
Given an array of integers & a positive integer target, return the minimal length subarray whose sum is at least the target. If no such subarray exists, return 0.
Explore
t=10
5 3 2 1 2 3 6 1 9
l r 10
l r 11
l r 14
l r 10
l r 16
l r 10
almin = l - r + 1
- almin = max int
- open window until sum >= target
- close window until sum < target updating array length min before each increment of l
- goto #2 while r < n
Python Solution
class Solution:
def min_subarray_length(self, t, a):
l, r, n, almin, rsum = 0, 0, len(a), len(a) + 1, 0
while r < n:
if rsum < t:
rsum += a[r]
r += 1
while rsum >= t:
almin = min(almin, r - l)
rsum -= a[l]
l += 1
return 0 if almin == n + 1 else almin
Repeated DNA Sequences
Given a DNA sequence, return all 10 letter substrings that occur more than once.
Explore
A A A A A C C C C C A A A A A C C C C C C A A A A A G G G T T T
l r
- Slide the window open to the first 10 letter long substring creating the current substring along the way.
- While sliding the window right until the end: a. Keep track of the current 10 letter substring as the window moves, i.e. add and remove the beginning & the end of the string each time. b. Check each 10 letter substring against a set. If it is in the set, add it to the solution.
- Return the solution substrings as an array.
Python Solution
from collections import Counter
class Solution:
def m(self, dna_sequence: str) -> List[str]:
l, r, n, a, css, pss = 0, 0, len(dna_sequence), dna_sequence, "", Counter()
soln = []
if n < 10:
return soln
while r < 10:
css += a[r]
r += 1
pss[css] += 1
while r < n:
css += a[r]
css = css[1:]
pss[css] += 1
if pss[css] == 2:
soln.append(css)
r += 1
return solnComplexity
We slide a fixed size window over an input sequence which takes 2n operations in the worst case, the one in which the window approaches the size of the input sequence. This take O(n) time & uses a hashmap which in this fixed sized window case takes O(n) space.
Shortest Subarray With OR at Least K II
Given a non-negative integer array & an integer K, return the shortest subarray with bitwise OR of at least K. Return -1 if no such array exists.
Explore
k=3 k=3 k=3
1 1 1 1 2 2 1 2 3
l r l r l r
-> -1 l r l r
-> 2 lr
-> 1
- Slide open a window until the bitwise OR of its elements >= K.
- Update the min length subarray.
- Slide window closed from the left until bitwise OR < K. a. Turns out that removing the leftmost integer is impossible without tracking which bits are attributed to which integer or keeping a running sum of each bit individually.
- GOTO #1.
Python Solution
from collections import Counter
class Solution:
def get_num(self, bor: dict) -> dict:
num = 0
for i in range(32):
if bor[i]:
num |= 1 << i
return num
def update_bor(self, bor: dict, a: int, u: int) -> dict:
for i in range(32):
if (a >> i) & 1:
bor[i] += u
return bor
def min_subarray_or_k(self, nums: List[int], k: int) -> int:
a, n, bor, l, r = nums, len(nums), Counter(), 0, 0
mlsarray = n + 1
# What are the edges cases?
if n == 0:
return -1
if k == 0:
return 1
while r < n:
bor = self.update_bor(bor, a[r], 1)
r += 1
while self.get_num(bor) >= k:
mlsarray = min(mlsarray, r - l)
bor = self.update_bor(bor, a[l], -1)
l += 1
return mlsarray if mlsarray < n + 1 else -1
3Sum
Given an integer array, return all unique triplets that sum to zero|target without replacement.
Explore
t = 2
-2 0 1 3
c l r
l r
- Sort the input.
- For all i, using t - i = c, find l + r = c by closing a window over the rest of the input.
Python Solution
class Solution:
def threeSum(self, a, t=0) -> List[List[int]]:
a.sort()
soln, unique, n = [], set(), len(a)
for i, x in enumerate(a):
c = t - x
l, r = i + 1, n - 1
while l < r:
s = a[l] + a[r]
if s < c:
l += 1
elif s > c:
r -= 1
else:
sl = [t - c, a[l], a[r]]
st = tuple(sorted(sl))
if st not in unique:
soln.append(sl)
unique.add(st)
l += 1
r -= 1
return soln
3Sum Smaller
Given an integer array, return the number of triplets, indices i<j<k, that sum to less that the target.
Explore
t < 2 t < 2 t < 2
-2 0 1 3 3 0 0 0 3 3 3 3
c l r 0 0 0 3 -> 0
l r c l r
-> 2 -> 1
Python Solution
class Solution:
def m(self, nums, target) -> int:
soln, N = 0, len(nums)
nums.sort()
for i, n in enumerate(nums):
c = target - n
l = i + 1
r = N - 1
while l < r:
if nums[l] + nums[r] < c:
# then all l+1...r-1 work as well
soln += r - l
l += 1
else:
r -= 1
return solnComplexity
In the worst case the sorting operation took nlogn time, then we performed nested iteration on the input resulting in an overall O(n^2) time & using constant O(1) space.
3Sum Closest
Given an integer array & target, find the three integers in the input such that their sum is closest to the target. Return their sum & assume their is exactly one solution.
Explore
t=9
1 2 3 4 5
1 l r
- Sort the input.
- Iterate the input using a sliding window on the subarray following the current index to find the three sum that minimizes the difference from the target.
Python Solution
import sys
class Solution:
def m(self, nums, target) -> int:
N, min, soln = len(nums), sys.maxsize, 0
nums.sort()
for i, n in enumerate(nums):
l, r = i + 1, N - 1
while l < r:
s = n + nums[l] + nums[r]
d = target - s
if abs(d) < abs(min):
min = d
soln = s
if s < target:
l += 1
else:
r -= 1
return solnComplexity
We sort the input in nlogn time & then perform a nested iteration using the sliding window from each index in the worst case for an O(n^2) runtime using constant, O(1), space.