Sliding Window Algorithm

Description

The Sliding Window algorithm is used for finding subarrays (or substrings) of a given size ( k ) with the maximum (or minimum) sum, or to solve other array-related problems efficiently. It operates by maintaining a window of size ( k ) over the array and sliding the window one element at a time to calculate the desired result without re-evaluating all elements.

C++ Code

#include <iostream>
#include <vector>
using namespace std;

int slidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    if (n < k) {
        return -1;
    }

    int maxSum = 0;
    for (int i = 0; i < k; ++i) {
        maxSum += nums[i];
    }

    int currentSum = maxSum;
    for (int i = k; i < n; ++i) {
        currentSum += nums[i] - nums[i - k];
        maxSum = max(maxSum, currentSum);
    }

    return maxSum;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;

    cout << "Maximum sum of subarray of size " << k << ": " << slidingWindow(nums, k) << endl;

    return 0;
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Sliding Window	O(n)	O(1)

Where:

• n: Number of elements in the input array.

← Back to Homepage