# Fixed size variant of Sliding window technique — Maximum Average Subarray1 (Leetcode)

**Problem Statement: **Here goes the brief description of the problem. Take your time in reading the complete problem statement here. **An array of integers **will be given along with the **window size K. **We need to calculate the average of all integers within that window and return maximum possible average.

**Bruteforce Method**: Traverse entire Array from 0 to n-k where k is the size of array. At each iteration calculate what we need and maintain one variable to store max_avg. Update max_avg each time and return at the last.

This is not a preferred method of solving this class of problems as it takes O(N*K) time complexity at the worst case.

**O(N) approach**: The same problem can be solved in O(N) time complexity if we understand one simple thing in the problem.

The sum of elements in the array from arr[1] to arr[3] = sum of elements upto arr[3] — arr[0]

Maintian a variable j that moves from 0th to last index of the array and another variable i that moves from 0th index to N-k index.

Sum is sum of arr[j] . If the distance between i and j = k, calculate sum .There onwards, whenever we increment i, also increment j and **subtract arr[i] from sum. **This gives the real sum of elemets of that window.

**JAVA Snippet:**

class Solution {

public double findMaxAverage(int[] nums, int k) {

double maxSum = Double.NEGATIVE_INFINITY;

int i= 0;

long sum = 0;

for(int j= 0;j<nums.length;j++){

sum+=nums[j];

if(j-i+1 == k){

if(sum>maxSum){

maxSum = sum;

}

sum-=nums[ws];

i++;

}

}

return maxSum/k;

}

}

**Idea behind the solution and Solving similar problems**: The key idea that makes the solution is A+B+C-A = B+C. If we remove an element from cumulative sum, we will get sum of a part of an array.

Similary, A^B^C^A = B^C. We need to know how to balance this equation in any fixed size window problem.

Check my submission for this problem here.