Coding Patterns: Sliding Window

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(n²) or O(n³) but using the 'sliding window' technique, we can reduce the time complexity to O(n).

 

Problem: Maximum Average Subarray:

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.       

 

 Sliding Window Solution:

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                                                                

 

1. We compute the sum of the first k elements out of n terms using a linear loop and store the sum in the variable max_sum.
2. Then we will graze linearly over the array till it reaches the end and simultaneously keep track of the maximum sum.
3. To get the current sum of a block of k elements just subtract the first element from the previous block and add the last element of the current block.

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.

• For example, if 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.

Solution:                                                                                      

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?                                                                                  

• The problem involves a data structure that is ordered and iterable like arrays, strings, etc.
• The problem is asking to find a subrange in an array/string, contiguous longest, shortest, average, max/min k-subarray, XOR, product, sum, or target value.
• There is an apparent naive or brute force solution that runs in O(N²), O(2^N), or some other large time complexity.

 

Similar LeetCode Problems:

• LeetCode 3 - Longest Substring Without Repeating Characters [medium]
• LeetCode 30 - Substring with Concatenation of All Words [hard]
• LeetCode 76 - Minimum Window Substring [hard]
• LeetCode 209 - Minimum Size Subarray Sum [medium]
• LeetCode 424 - Longest Repeating Character Replacement [medium]
• LeetCode 438 - Find All Anagrams in a String [medium]
• LeetCode 567 - Permutation in String [medium]
• LeetCode 904 - Fruit Into Baskets [medium]
• LeetCode 1004 - Max Consecutive Ones III [medium]