Solving Maximum Average Subarray I

To see the question, click here.

Naive Approach

The idea is to calculate the sum of every k consecutive integers and then find the maximum sum, giving us the maximum average. So, maintain two pointers i and j at the first position of the array. i will move until nums.length - k and j will move until i + k - 1 . Keep track of the maximum sum and return the maximum average.

// TC: O(n*k)
// SC: O(1)

public class MaximumAverageSubarrayI {
    public double findMaxAverage(int[] nums, int k) {
        double maxSum = Double.NEGATIVE_INFINITY;
        for (int i = 0; i <= nums.length - k; i++) {
            double currSum = 0;
            for (int j = i; j < i + k; j++) {
                currSum += nums[j];
            }
            maxSum = Math.max(maxSum, currSum);
        }
        return maxSum / k;
    }

    public static void main(String[] args) {
        MaximumAverageSubarrayI mas = new MaximumAverageSubarrayI();
        int[] nums = { 1, 12, -5, -6, 50, 3 };
        int k = 4;
        System.out.println(mas.findMaxAverage(nums, k));
    }
}

Performance

The time complexity of the findMaxAverage method is O(n*k) because there are two nested loops - one iterating through the array and another through the subarray of size k. The space complexity is O(1) because the algorithm uses constant extra space regardless of the input size.

Refined Approach

The idea is to use the concept of prefix sums to efficiently calculate the sum of elements in a subarray of an array. First, create a new array prefixSums with a length one more than the original array nums. Set the first element of prefixSums is to 0. For each element in the original array nums, the corresponding element in prefixSums is calculated by adding the current element of nums to the previous element's value in prefixSums i.e., prefixSums[i + 1] = prefixSums[i] + nums[i] . Thus, prefixSums[i] represents the sum of elements from nums[0] to nums[i-1].

To find the sum of any subarray from the index i to j in nums, you can subtract prefixSums[i] from prefixSums[j+1]. This works because prefixSums[j+1] contains the sum of elements from nums[0] to nums[j], and prefixSums[i] contains the sum of elements from nums[0] to nums[i-1]. Subtracting these gives the sum of the subarray from i to j.

So, for each possible subarray of length k calculate the sum by subtracting the prefix sum just before the subarray starts from the prefix sum at the end of the subarray i.e., prefixSums[i] - prefixSums[i - k] where i starts from k. Keep track of the maximum sum and return the maximum average.

// TC: O(n)
// SC: O(n)

public class MaximumAverageSubarrayI {
    public double findMaxAverage(int[] nums, int k) {
        int[] prefixSums = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefixSums[i + 1] = prefixSums[i] + nums[i];
        }

        double maxSum = Double.NEGATIVE_INFINITY;
        for (int i = k; i < prefixSums.length; i++) {
            double currSum = prefixSums[i] - prefixSums[i - k];
            maxSum = Math.max(maxSum, currSum);
        }
        return maxSum / k;
    }

    public static void main(String[] args) {
        MaximumAverageSubarrayI mas = new MaximumAverageSubarrayI();
        int[] nums = { 1, 12, -5, -6, 50, 3 };
        int k = 4;
        System.out.println(mas.findMaxAverage(nums, k));
    }
}

Performance

The time complexity of the findMaxAverage method is O(n) because we iterate through the prefixSums array once to calculate the prefix sums and then iterate through it again to find the maximum average subarray. The space complexity is also O(n) because we create an additional array prefixSums of size n+1 to store the prefix sums.

Efficient Approach

Since we deal with a problem involving consecutive elements, let us try the Sliding Window technique. So, define a window of size k, maintain two pointers windowStart and windowEnd at the first position of the array. Find out the window's sum by moving windowEnd till k. Until windowEnd reaches n-1, slide the window, i.e., add the number at windowEnd and subtract the number at windowStart . This is the key step because when the window slides, the element at the first position of the previous window disappears, and the element at the last position of the new window appears. Keep track of the maximum sum by comparing it with the window's sum and return the maximum average.

// TC: O(n)
// SC: O(1)

public class MaximumAverageSubarrayI {
    public double findMaxAverage(int[] nums, int k) {
        double windowSum = 0, maxSum = Double.NEGATIVE_INFINITY;

        int windowStart = 0, windowEnd = 0, n = nums.length;

        while (windowEnd < n) {

            if (windowEnd < k) {
                windowSum += nums[windowEnd];
                windowEnd++;
            }

            else {
                maxSum = Math.max(maxSum, windowSum);
                windowSum -= nums[windowStart];
                windowStart++;
                windowSum += nums[windowEnd];
                windowEnd++;
            }
        }

        maxSum = Math.max(maxSum, windowSum);

        return maxSum / k;
    }

    public static void main(String[] args) {
        MaximumAverageSubarrayI mas = new MaximumAverageSubarrayI();
        int[] nums = { 1, 12, -5, -6, 50, 3 };
        int k = 4;
        System.out.println(mas.findMaxAverage(nums, k));
    }
}

Performance

The time complexity of the findMaxAverage method is O(n) because we iterate through the entire array of length n once. The space complexity is O(1) because we only use constant extra space regardless of the input size.

Thank you for reading!

Check out other DSA patterns here.

You can support me by buying me a book.