Java Sliding Window solution O(N) time O(1) space


  • 0

    This overall is an easy problem. The naive way would be to iterate every i and find the one that has the maximum average over the k elements following nums[i].

    Slight optimization inspired by the Sliding Window algorithm: instead of recalculating the average of the length-k window at each position i, we maintain a variable sum so that all we need to do at entry i is to add nums[i - k + 1] and subtract nums[i - 1]. Everything else is just intuitive.

    public class Solution {
        public double findMaxAverage(int[] nums, int k) {
            int n = nums.length;
            int sum = 0;
            for (int i = 0; i < k; i++) sum += nums[i];
            if (n <= k) return (double) sum / k;
            int maxSum = sum;
            for (int i = 1; i < n - k + 1; i++) {
                sum += nums[i + k - 1] - nums[i - 1];
                if (sum > maxSum) maxSum = sum;
            }
            return (double) maxSum / k;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.