Sliding Windows Problem Introduction
- Linked list or arrays find something among all contigious sub array of some given size.
Example problem
Given an array, find the average of all contiguous subarrays of size ‘K’ in it.
For a given array: \([1, 3, 2, 6, -1, 4, 1, 8, 2]\) and \(K=5\) means find the average of all the contiguous subarrays of size ‘5’ in the given array.
- For the first 5 numbers (subarray from index 0-4), the average is \((1+3+2+6−1)/5=2.2\)
- The average of next 5 numbers (subarray from index 1-5) is: \((3+2+6-1+4)/5 = 2.8\)
- For the next 5 numbers (subarray from index 2-6), the average is: 2.5 and so on.
Here is the final output containing the averages of all contiguous subarrays of size 5: Output: [2.2, 2.8, 2.4, 3.6, 2.8]
Brute force apprach
A brute-force algorithm will be to calculate the sum of every 5-element contiguous subarray of the given array and divide the sum by ‘5’ to find the average.
def brute_force(array: list[int], K:int) -> list[int]:
# Keep track of the avgs
avgs: list[int] = []
# Start from 0 and go to the next 5 elements and find the average
for i in range(0, len(array)- K+1):
sum: int = 0
for j in range(i, i+K):
sum += array[j]
avg: float = sum / K
avgs.append(avg)
return avgs
mainarray: list[int] = [1, 3, 2, 6, -1, 4, 1, 8, 2]
K: int = 5 # find max of this size for given array
a: list[int] = brute_force(mainarray, K)
from rich.console import Console # For printing purposes
console = Console()
console.print(a)
Problems with this apporach
- Time complexity is huge \(O(N * K)\).
- We are summing up same elements over and over again. For two consecutive subarrays of size 5 we could just add the new incoming elements and subtract the outgoing elements.
This will reduce the cost to \(O(N)\) with just one time \(O(K)\) summing up program.
def optimized(array: list[int], K: int) -> list[int]:
if K > len(array):
raise IndexError("Error Bro")
# Keep track of all the averages
avgs: list[int] = []
# Start from 0 and go to the next K elements and find the average
sumtillK: int = 0
for i in range(0, K):
sumtillK += array[i]
avgs.append(sumtillK / K)
# If the size of the array is the size of the window then just return
if K == len(array):
return avgs
# From K+1 to Last element for each sliding window add the last
# element and subtract the first element
# Leave the first element and then start from 2nd elemenet
# and slide smoothly
for i in range(1, len(array) - K + 1):
sumtillK = sumtillK - array[i - 1] + array[i + K - 1]
avgs.append(sumtillK / K)
return avgs
Optimized approach with while loop
def optimized_while(array: list[int], K: int) -> list[int]:
avgs: list[int] = []
if K > len(array):
raise IndexError("Error Bro")
sumtillk: int = 0
for i in range(0, K):
sumtillk += array[i]
avgs.append(sumtillk / K)
# Leave the first element and then start from 2nd elemenet
# and slide smoothly
index: int = 1
while index != (len(array) - K + 1):
sumtillk = sumtillk - array[index - 1] + array[index + K - 1]
avgs.append(sumtillk / K)
index += 1
return avgs
b: list[int] = optimized(mainarray, K)
c: list[int] = optimized_while(mainarray, K)
console.print(b)
console.print(c)
Output
Maximum Sum subarray of size K
Problem Statement
Given an array of positive numbers and a positive number ‘k’, find the maximum sum of any contiguous subarray of size ‘k’.
Examples
Input: [2, 1, 5, 1, 3, 2], k=3
Output: 9
Explanation: Subarray with maximum sum is [5, 1, 3].
---
Input: [2, 3, 4, 1, 5], k=2
Output: 7
Explanation: Subarray with maximum sum is [3, 4].
Approach [Naive on back of the envelope approach]
def mss(array: list[int], k:int) -> int:
maximum: int = 0
sumtillK: int = 0
for i in range(0, k):
sumtillK += array[i]
maximum = sumtillK
idx: int = 1
while idx != len(array) - k:
sumtillK = sumtillK - array[idx-1] + array[idx + k -1]
maximum = max(maximum, sumtillK)
idx += 1
return maximum
mainarray: list[int] = [2, 1, 5, 1, 3, 2]
K: int = 3 # find max of this size for given array
a2: list[int] = [2, 3, 4, 1, 5]
k2 = 2
Time complexity
Only one pass of the array so the time complexity is \(O(N)\)
Smallest subarray with a given sum
Problem statement
Given an array of positive numbers and a positive number ‘S’, find the length of the smallest contiguous subarray whose sum is greater than or equal to ‘S’. Return 0, if no such subarray exists.
Examples
Input: [2, 1, 5, 2, 3, 2], S=7
Output: 2
Explanation: The smallest subarray with a sum great than or equal to '7' is [5, 2].
---
Input: [2, 1, 5, 2, 8], S=7
Output: 1
Explanation: The smallest subarray with a sum greater than or equal to '7' is [8].
---
Input: [3, 4, 1, 1, 6], S=8
Output: 3
Explanation: Smallest subarrays with a sum greater than or equal to '8' are [3, 4, 1] or [1, 1, 6].
Brute force approach
Key takeway approach
💡 For each size of window find out if the sum is greater or equal to the target?
testcase1: list[int] = [2, 1, 5, 2, 3, 2]
testcase1s: int = 7
testcase2: list[int] = [3, 4, 1, 1, 6]
testcase2s: int = 8
testcase3: list[int] = [2, 1, 5, 2, 8]
testcase3s: int = 7
# Brute force approach
def ssgs(array: list[int], s: int) -> int:
def subroutine(array: list[int], ws: int, target: int):
if ws == 1:
for entires in array:
if entires >= target:
return 1
summation: int = 0
for i in range(0, ws):
summation += array[i]
if summation >= target:
return ws
index = 1
while index < len(array) - ws:
summation = summation - array[index - 1] + array[index + ws - 1]
if summation >= target:
return ws
index += 1
return -1
window_size: int = 1
subroutine_return: int = -1
while window_size < len(array) and subroutine_return == -1:
subroutine_return = subroutine(array, window_size, s)
window_size += 1
return subroutine_return
console.print(ssgs(testcase1, testcase1s),
ssgs(testcase2, testcase2s),
ssgs(testcase3, testcase3s),
ssgs([1, 2, 10, 3, 4, 5, 6, 7, 8], 17))
Time complexity
\(O(N)\) work for each size of the window and at most \(N\) is the windows size. So \(N*O(N) = O(N^2)\)
Better Optimized approach
- First we add up the elements of the array from start until we get the sum at least the target
- This is the first window size from the array that at least sums upto the target, so we remember the length
- We will remember the length of the window if we find a smaller window than this that sums at least the target.
Coming soon
Room for more understanding
...
Longest Substring with K Distinct Characters
Problem statement
Given a string, find the length of the longest substring in it with no more than K distinct characters.
Input: String="araaci", K=2
Output: 4
Explanation: The longest substring with no more than '2' distinct characters is "araa".
Comments
This comments system is powered by GitHub Discussions