Average Subarray Walmart Python Interview Question

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

Your task is to find a contiguous subarray of whose length is exactly that has the highest average value. A subarray is simply a sequence of consecutive elements from the original array. After identifying this subarray, return the average value, rounded to two decimal places.

Example #1

Input: nums = [1, 2, -5, -3, 10, 3], k = 3

Output: 3.33

Explanation: The subarray here is , so the average is 3.33.

Example #2

Input: nums = [9], k = 1

Output: 9.00

Explanation: The subarray here is just , so its average is exactly 9.00.

Brute Force Approach

In a coding interview, you are not expected to come up with the most optimal solution right away. Typically, you start from a brute force approach and then improve it as you go.

The straightforward way to solve this problem is to start at each index, sum the next elements, keep track of the maximum sum, and return the average by dividing that sum by . While this approach works, it isn't the most efficient.

Here is the brute force solution:

Prefix Sum Approach

Intuition

If you are not familiar with the prefix sum technique, it's a common strategy used to calculate ranges of sums efficiently. You can learn more about it here. The idea is that, by storing the cumulative sum of elements before each index, we can quickly compute the sum of any subarray in constant time.

For example, consider the array:

and

We can build the prefix sum array like this:

Each number in represents the sum of all elements before that index (not including the index itself). So, means that the sum of the first three elements of is .

Now, let’s say we want the sum of the subarray . We can simply subtract from . This gives us the sum of the subarray, without recalculating the sum from scratch each time.

This is much faster than recalculating sums every time!

Here’s how we can implement this approach:

Sliding Window Approach

The sliding window technique improves on the brute force method by eliminating the need to re-sum all elements in the window each time. Instead, we maintain a running sum of the current elements and update it efficiently as we 'slide' the window across the array.

If you are not familiar with the sliding window technique, you can learn more about it here.

The trick is simple:

• First, sum the first elements to initialize the window.
• Then, as you move the window one element to the right, you add the next element and subtract the element that is now out of the window.
• Update the maximum sum if the new window sum is larger.

Example:

For and , the sum of the first three elements is . When we move the window one step to the right, we subtract (which is now out of the window) and add , giving a new sum of .

Here is the implemetation: