Sliding Windows

Have a computation window and keep moving/adjusting

Ways to indentify

• Input is linkedlist or array
• Find longest/shortest substring, sub array or desired value

Time complexity

• Time: O(n) because each element visited at most twice
• Space O(1)

To read https://medium.com/leetcode-patterns/leetcode-pattern-2-sliding-windows-for-strings-e19af105316b

Example

Given an array of integers of size **‘n’**.  
Our aim is to calculate the maximum sum possible for **‘k’** consecutive elements in the array.  
  
Input : arr[] = {100, 200, 300, 400}  
k = 2  
Output : 700

Bruteforce:

for(int i = 0; i < n-k+1; i++){      
    int current_sum = 0;  
       
    for(int j = 0; j < k; j++){          
        current_sum = current_sum + arr[i+j];           
    }    
    
    max_sum = max(current_sum, max_sum); // pick maximum sum   
}

Time: O($n^2$)
Space: O(1)

Sliding windows

def max_k(arr, k):
	tmp_sum = 0
	for i in range(0, k):
		tmp_sum += arr[i]
	for i in range(k, len(arr)):
		tmp_sum = max(tmp_sum, tmp_sum - arr[i - k] + arr[i]) 
		# Get rid of left number and add right number
	return tmp_sum

Time: O(n)
Space: O(1)

Note: for find max sub-array at any size k, consider Maximum Subarray (Kadane's Algorithm)