Sliding Window Technique

reference

Sliding window technique improves the efficiency of iteration from O(n*k) to O(n)

Example

Given an array of integers of size ‘n’. Our aim is to calculate the maximum sum of ‘k’ consecutive elements in the array.

A brute Force Solution to this problem would be the following:

int maxSum(int arr[], int n, int k) 
{ 
    // Initialize result 
    int max_sum = INT_MIN; 
  
    // Consider all blocks starting with i. 
    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]; 
  
        // Update result if required. 
        max_sum = max(current_sum, max_sum); 
    } 
  
    return max_sum; 
} 

Time Complexity : O(n*k)

With sliding window technique, we can have a window of k elements and keep track of the current sum of the k element sand the maximum sum found so far. We can slide this window through the array to find the answer.

int maxSum(int arr[], int n, int k) 
{ 
    // n must be greater 
    if (n < k) { 
        cout << "Invalid"; 
        return -1; 
    } 
  
    // Compute sum of first window of size k 
    int max_sum = 0; 
    for (int i = 0; i < k; i++) 
        max_sum += arr[i]; 
  
    // Compute sums of remaining windows by 
    // removing first element of previous 
    // window and adding last element of 
    // current window. 
    int window_sum = max_sum; 
    for (int i = k; i < n; i++) { 
        window_sum += arr[i] - arr[i - k]; 
        max_sum = max(max_sum, window_sum); 
    } 
  
    return max_sum; 
} 

Time Complexity : O(n)

Uses

1. Sequentially iterate over
   • contiguous sequence of elements
   • strings, arrays, linked list
2. To find min, max, longest, shortest, or whether contained
   • may need calculation and record some value

Learn about Dynamic Version of Sliding Window Technique