Sliding Window: Given an array and a value k, find the maximum average subarray

Problem Statement:

You are given an array and a value k.

You need to find the subarray of value k that has the maximum average value.

You need to return the value.

Example:

Input: [1, 2, 3, 4] k =2

Output: 3.5

Explanation: [3 + 4] = 7/2 = 3.5

Solution Explanation:

We will use sliding window approach to solve the problem.

Initialize a window of size k.

Initialize 2 variable, maxSum and currSum and calculate the value and update the maxSum value accordingly.

At the end take the average and return the result.

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

Code Solution

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


double solution(vector<int>& nums, int k) 
{
    double sum = 0;

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

    double maxSum = sum;

    // sliding window
    for (int i = k; i < nums.size(); i++) 
    {
        sum = sum - nums[i - k] + nums[i]; 
        maxSum = max(maxSum, sum);
    }

    return maxSum / k;  
}

int main() 
{
    vector<int> arr = {1, 2, 3, 4};
    int k = 2;
    cout << solution(arr, k) << endl;
    return 0;
}

Output

3.5