Fixed Size Sliding Window Algorithm with Example.

The Fixed Size Sliding Window Algorithm is a powerful technique used in computer programming and data processing to efficiently process data in a sliding window fashion. This algorithm is particularly useful when dealing with large data sets or solving problems involving continuous or sequential data processing.

Here in this article, we are going to cover Fixed-Size Sliding Window Algorithm in detail with Example.  

When to use Fixed Size Sliding Window Algorithm? 

The Fixed Size Sliding Window Algorithm is particularly useful in scenarios where you need to efficiently process sequential data by maintaining a fixed-size subset or window of elements. 

Here are some situations where this algorithm can be beneficial:

• Subarray/Substring Problems: When you need to solve problems that involve finding the maximum or minimum sum, product, or average of a contiguous subarray or substring within a larger array or string.

• Sequential Data Processing: When you need to process data in a sequential manner, such as time series data, sensor readings, or log files, and perform calculations or computations on a fixed-size subset of the data.

• Windowed Aggregations: When you need to compute aggregate values (e.g., sum, average, maximum, minimum) over a sliding window of elements in a time-based or sequential data stream.

• Pattern Matching: When you need to identify or search for specific patterns or sequences within a larger sequence or stream of data.

Algorithm of Fixed Size Sliding Window.

The Fixed Size Sliding Window Algorithm involves maintaining a fixed-size window or subset of elements as it slides through the input data. The window moves one element at a time, allowing for efficient data processing and analysis. 

The algorithm typically follows these steps:

Step 1: Initialize the window with the first 'k' elements from the input data, where 'k' is the desired window size.

Step 2: Process the initial window to perform any required calculations or operations.

Step 3: Slide the window by moving one element forward.

Step 4: Update the window by adding the next element from the input data and removing the last element from the previous window.

Step 5: Perform the necessary computations or operations on the updated window.

Step 6: Repeat steps 3-5 until the end of the input data is reached.

So these are steps that you need to follow to solve any fixed-size sliding window problem, let's understand the algorithm in more detail with one example.

Example of Fixed Size Sliding Window.

Given an array of size n, we need to find the maximum sum of k consecutive elements in the array. 

Example:

Input: num[] = {2, 3, 5, 4, 9, 7, 1}  k = 3
Output: 20

Explanation: 
The sum of all possible subarrays of size 3
{2, 3, 5} = 2+3+5 = 10
{3, 5, 4} = 3+5+4 = 12
{5, 4, 9} = 5+4+9 = 18
{4, 9, 7} = 4+9+7 = 20
{9, 7, 1} = 9+7+1 = 17 
The maximum sum we get by adding the subarray {4, 9, 7} of size 3.

//C++ Program to Find Max Sum of Window Size K
#include <iostream>
#include <vector>
using namespace std;

int maxSumInSlidingWindow(const vector<int>& nums, int k) {
    int windowSum = 0;
    int maxSum = 0;

    // Calculate the initial window sum
    for (int i = 0; i < k; ++i) {
        windowSum += nums[i];
    }

    maxSum = windowSum;

    // Slide the window and update the maximum sum
    for (int i = k; i < nums.size(); ++i) {
        windowSum += nums[i] - nums[i - k];
        maxSum = max(maxSum, windowSum);
    }

    return maxSum;
}

int main() {
    vector<int> nums = {2, 3, 5, 4, 9, 7, 1};
    int k = 3;

    int maxSum = maxSumInSlidingWindow(nums, k);

    cout << "Maximum sum of " << k << " consecutive elements: " << maxSum << endl;

    return 0;
}

Maximum sum of 3 consecutive elements: 20