The Sliding window is a problem-solving technique that aims to reduce the use of nested loop and replace it with a single loop, thereby reducing the time complexity. These problems are easy to solve using a brute force approach in O(n2) or O(n3) but using the 'sliding window' technique, we can reduce the time complexity to O(n).
LeetCode 643 - Maximum Average Subarray I [easy]
You are given an integer array nums
consisting of n
elements, and an integer k
.
Brute Force Solution:
We start with first index and sum till k-th element. We do it for all possible consecutive blocks or groups of k elements. This method requires nested for loop, the outer for loop starts with the starting element of the block of k elements and the inner or the nested loop will add up till the k-th element.
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
max_value = 0
for i in range(len(nums) - k + 1):
sum = 0
for j in range(i, i + k):
sum += nums[j]
max_value = max(max_value, sum)
return max_value / k
Time Complexity: O(n*k) where n is the number of elements in the input array.
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
# Compute sum of first window of size k
max_sum = sum(nums[:k])
result = max_sum # first sum available
for i in range(k, len(nums)):
max_sum += nums[i] - nums[i - k]
result = max(max_sum, result)
return result / k
Time Complexity is linear as we can see that only one loop runs in our code. Hence, our Time Complexity is O(n).
Problem: Substring with Concetenation of All words:
Leetcode - 30. Substring with Concatenation of All Words
You are given a string s
and an array of strings words
. All the strings of words
are of the same length.
A concatenated substring in s
is a substring that contains all the strings of any permutation of words
concatenated.
words = ["ab","cd","ef"]
, then "abcdef"
, "abefcd"
, "cdabef"
, "cdefab"
, "efabcd"
, and "efcdab"
are all concatenated strings. "acdbef"
is not a concatenated substring because it is not the concatenation of any permutation of words
.Return the starting indices of all the concatenated substrings in s
. You can return the answer in any order.
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
n=len(words) * len(words[0])
n1=len(words[0])
arr=[]
words.sort()
words=''.join(words)
for i in range(0,len(s)-n+1):
temp=s[i:i+n]
parts=[temp[i:i+n1] for i in range(0,len(temp),n1)]
parts.sort()
parts=''.join(parts)
if(parts==words):
arr.append(i)
return arr
How to identify?