643. Maximum Average Subarray I

Maximum Average Subarray I

Problem Description

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

Example 1:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Example 2:

Input: nums = [5], k = 1
Output: 5.00000

Constraints:

• n == nums.length
• 1 <= k <= n <= 105
• -104 <= nums[i] <= 104

Idea:

This problem is relatively simple.

• Each time you move ​k, find the sum of the elements of the box. When you move the box to the right.
• add a new element to the box and remove the first element in the box.
• updates the maximum value of the sum of consecutive subarrays.

Let`s Code it!

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findMaxAverage = function(nums, k) {
    let kSum = 0;
    for(let i=0;i<k;i++){
        kSum += nums[i];
    }
    let windowSum = kSum;
    for(let i=0;i<nums.length;i++){
        windowSum = windowSum + nums[i+k] - nums[i];
        if(windowSum > kSum){
             kSum = windowSum;
        }
    }
    return kSum/k;
};

Complexity 

Time Complexity
We are scanning the string from left to right only once, hence the time complexity will be O(n).


Space Complexity
We are using kSum as a constant to facilitate our computation, therefore, the space complexity should also be O(1).

Conclusion

That’s all folks! In this post, we solved LeetCode problem #643. Maximum Average Subarray I using Sliding Window Technique.

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!