Jobs

Interviews

Discussions

Maximum Average Subarray II

Hard

Asked by:

26 views

Topics:

ArraysBinary Search

Given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is greater than or 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:
When length is 5, maximum average value is 10.8.
When length is 6, maximum average value is 9.16667.
Thus answer is 12.75000.

Example 2:

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

Constraints:

n == nums.length
1 <= k <= n <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Try coding it in LeetCode

Maximum Average Subarray II

Hard

Asked by:

26 views

Topics:

ArraysBinary Search

Given an integer array nums consisting of n elements, and an integer k.

Example 1:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation:
When length is 5, maximum average value is 10.8.
When length is 6, maximum average value is 9.16667.
Thus answer is 12.75000.

Example 2:

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

Constraints:

n == nums.length
1 <= k <= n <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for elements within the input array `nums`, and what is the maximum possible length of the array?
Can the input array `nums` be empty, and if so, what should I return?
Is `k` guaranteed to be a valid value, meaning `1 <= k <= n`, where `n` is the length of the array?
If there are multiple subarrays with the same maximum average, is any one of them acceptable, or is there a specific requirement for which one to return (e.g., the first occurrence)?
Can I return the average directly as a double, or do I need to return the indices of the subarray?

Brute Force Solution

Approach

The brute force approach for finding the maximum average involves checking every possible group of numbers. We calculate the average for each group we try. Ultimately, we compare all of the averages and return the largest one we found.

Here's how the algorithm would work step-by-step:

Start by considering the first possible group size, which is the smallest allowed size.
Calculate the average of the first group of numbers with that size.
Move the group one position over and calculate the average again.
Continue shifting the group and calculating the average until you reach the end of the number list.
Increase the group size by one, up to the maximum allowed size.
Repeat the process of shifting the group and calculating the average for this new group size.
Keep doing this until you've considered all possible group sizes and positions.
Finally, go through all the calculated averages and find the largest one. That's your maximum average.

Code Implementation

def find_max_average_brute_force(numbers, minimum_group_size):
    maximum_average = float('-inf')

    # Iterate through all possible group sizes
    for current_group_size in range(minimum_group_size, len(numbers) + 1):

        # Iterate through all possible starting positions for the current group size
        for start_index in range(len(numbers) - current_group_size + 1):
            current_sum = 0
            # Calculate the sum of the current group
            for index in range(start_index, start_index + current_group_size):
                current_sum += numbers[index]

            current_average = current_sum / current_group_size

            # Keep track of the highest average
            if current_average > maximum_average:
                maximum_average = current_average

    return maximum_average

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates through all possible subarray lengths, from k to n, where k is the minimum subarray length. The inner loop then iterates through the array calculating the average of each subarray of the current length. In the worst case, the outer loop runs approximately n times and the inner loop also runs approximately n times for each iteration of the outer loop. This results in roughly n * n operations, which simplifies to O(n²).

Space Complexity

O(1) – The described brute force approach calculates the average for each subarray within the given array of N numbers. It does not create any auxiliary data structures like arrays, lists, or hash maps to store intermediate results or track visited elements. Only a few constant space variables are needed to store the current group's sum, average, and the overall maximum average found so far. Therefore, the auxiliary space used is independent of the input size N, resulting in a space complexity of O(1).

Optimal Solution

Approach

The goal is to find the segment with the highest average. Instead of checking every possible segment, we'll use a clever technique to efficiently narrow down our search by guessing the average and checking if it's possible to find a segment with at least that average.

Here's how the algorithm would work step-by-step:

First, figure out the range of possible averages by finding the smallest and largest values in the set of numbers.
Make a guess for the average that's somewhere in the middle of the range.
Check if there's a segment of numbers that has an average at least as big as our guess. To do this, subtract the guessed average from each number in the set, and see if any consecutive group of numbers adds up to a positive value, given the minimum length constraint.
If we find a segment that's at least as big as our guess, we know our guess might be too low, so increase the guess. Otherwise, if we can't find such a segment, it means our guess is too high, so decrease the guess.
Keep repeating steps 2-4, making our guesses more and more accurate, until we find the true maximum average or get very, very close to it.

Code Implementation

def find_maximum_average(nums, minimum_length):
    lower_bound = min(nums)
    upper_bound = max(nums)

    # Binary search to find the maximum average.
    while upper_bound - lower_bound > 1e-5:
        mid_point = (lower_bound + upper_bound) / 2
        if check_average(nums, minimum_length, mid_point):
            lower_bound = mid_point
        else:
            upper_bound = mid_point

    return lower_bound

def check_average(nums, minimum_length, average):
    modified_numbers = [number - average for number in nums]
    current_sum = 0
    previous_sum = 0
    
    # Ensure that subarray of length >= min_length exists with average >= mid.
    for i in range(minimum_length):
        current_sum += modified_numbers[i]

    if current_sum >= 0:
        return True

    for i in range(minimum_length, len(nums)): 
        current_sum += modified_numbers[i]
        previous_sum += modified_numbers[i - minimum_length]

        # Keep track of min_sum to check for positive sum subarray.
        min_sum = min(0, previous_sum)

        # The segment average is not less than the mid point.
        if current_sum - min_sum >= 0:
            return True

    return False

Big(O) Analysis

Time Complexity

O(n log(maxVal - minVal)) – The algorithm performs a binary search on the range of possible average values, from minVal to maxVal. The binary search loop continues until the difference between the upper and lower bounds converges (or reaches a predetermined level of precision). Within each iteration of the binary search, we iterate through the array of n numbers once to check if there is a subarray of length k or greater with an average greater than or equal to our current guess. Therefore, the check function has O(n) complexity and is called log(maxVal - minVal) times within the binary search, yielding an overall time complexity of O(n log(maxVal - minVal)).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It only needs to store a few variables such as the current guess for the average and temporary sums during the checking phase. The space used does not depend on the input size N (the number of elements in the input array), therefore the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array	Return 0 if the array is empty, as there's no subarray.
k is larger than the array size	Return 0 because a subarray of size k cannot exist.
Array contains only one element, and k=1	Return the single element's value as the maximum average.
Array contains all negative numbers	The maximum average will be the least negative number or the average of the k smallest negative numbers.
Array contains large positive and negative numbers, potential for overflow	Use double precision floating-point numbers to calculate sums and averages to avoid integer overflow.
Array contains all zeros	The maximum average subarray will be 0.
k is equal to the array size	Return the average of all elements in the array.
Floating-point precision issues during binary search	Use a small epsilon value for comparing doubles to handle potential floating-point precision errors.

Empty input array

How to Handle:

Return 0 if the array is empty, as there's no subarray.

k is larger than the array size

How to Handle:

Return 0 because a subarray of size k cannot exist.

Array contains only one element, and k=1

How to Handle:

Return the single element's value as the maximum average.

Array contains all negative numbers

How to Handle:

The maximum average will be the least negative number or the average of the k smallest negative numbers.

Array contains large positive and negative numbers, potential for overflow

How to Handle:

Use double precision floating-point numbers to calculate sums and averages to avoid integer overflow.

Array contains all zeros

How to Handle:

The maximum average subarray will be 0.

k is equal to the array size

How to Handle:

Return the average of all elements in the array.

Floating-point precision issues during binary search

How to Handle:

Use a small epsilon value for comparing doubles to handle potential floating-point precision errors.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for elements within the input array `nums`, and what is the maximum possible length of the array?
Can the input array `nums` be empty, and if so, what should I return?
Is `k` guaranteed to be a valid value, meaning `1 <= k <= n`, where `n` is the length of the array?
If there are multiple subarrays with the same maximum average, is any one of them acceptable, or is there a specific requirement for which one to return (e.g., the first occurrence)?
Can I return the average directly as a double, or do I need to return the indices of the subarray?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering the first possible group size, which is the smallest allowed size.
Calculate the average of the first group of numbers with that size.
Move the group one position over and calculate the average again.
Continue shifting the group and calculating the average until you reach the end of the number list.
Increase the group size by one, up to the maximum allowed size.
Repeat the process of shifting the group and calculating the average for this new group size.
Keep doing this until you've considered all possible group sizes and positions.
Finally, go through all the calculated averages and find the largest one. That's your maximum average.

Code Implementation

def find_max_average_brute_force(numbers, minimum_group_size):
    maximum_average = float('-inf')

    # Iterate through all possible group sizes
    for current_group_size in range(minimum_group_size, len(numbers) + 1):

        # Iterate through all possible starting positions for the current group size
        for start_index in range(len(numbers) - current_group_size + 1):
            current_sum = 0
            # Calculate the sum of the current group
            for index in range(start_index, start_index + current_group_size):
                current_sum += numbers[index]

            current_average = current_sum / current_group_size

            # Keep track of the highest average
            if current_average > maximum_average:
                maximum_average = current_average

    return maximum_average

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out the range of possible averages by finding the smallest and largest values in the set of numbers.
Make a guess for the average that's somewhere in the middle of the range.
Check if there's a segment of numbers that has an average at least as big as our guess. To do this, subtract the guessed average from each number in the set, and see if any consecutive group of numbers adds up to a positive value, given the minimum length constraint.
If we find a segment that's at least as big as our guess, we know our guess might be too low, so increase the guess. Otherwise, if we can't find such a segment, it means our guess is too high, so decrease the guess.
Keep repeating steps 2-4, making our guesses more and more accurate, until we find the true maximum average or get very, very close to it.

Code Implementation

def find_maximum_average(nums, minimum_length):
    lower_bound = min(nums)
    upper_bound = max(nums)

    # Binary search to find the maximum average.
    while upper_bound - lower_bound > 1e-5:
        mid_point = (lower_bound + upper_bound) / 2
        if check_average(nums, minimum_length, mid_point):
            lower_bound = mid_point
        else:
            upper_bound = mid_point

    return lower_bound

def check_average(nums, minimum_length, average):
    modified_numbers = [number - average for number in nums]
    current_sum = 0
    previous_sum = 0
    
    # Ensure that subarray of length >= min_length exists with average >= mid.
    for i in range(minimum_length):
        current_sum += modified_numbers[i]

    if current_sum >= 0:
        return True

    for i in range(minimum_length, len(nums)): 
        current_sum += modified_numbers[i]
        previous_sum += modified_numbers[i - minimum_length]

        # Keep track of min_sum to check for positive sum subarray.
        min_sum = min(0, previous_sum)

        # The segment average is not less than the mid point.
        if current_sum - min_sum >= 0:
            return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 if the array is empty, as there's no subarray.
k is larger than the array size	Return 0 because a subarray of size k cannot exist.
Array contains only one element, and k=1	Return the single element's value as the maximum average.
Array contains all negative numbers	The maximum average will be the least negative number or the average of the k smallest negative numbers.
Array contains large positive and negative numbers, potential for overflow	Use double precision floating-point numbers to calculate sums and averages to avoid integer overflow.
Array contains all zeros	The maximum average subarray will be 0.
k is equal to the array size	Return the average of all elements in the array.
Floating-point precision issues during binary search	Use a small epsilon value for comparing doubles to handle potential floating-point precision errors.

Empty input array

How to Handle:

Return 0 if the array is empty, as there's no subarray.

k is larger than the array size

How to Handle:

Return 0 because a subarray of size k cannot exist.

Array contains only one element, and k=1

How to Handle:

Return the single element's value as the maximum average.

Array contains all negative numbers

How to Handle:

The maximum average will be the least negative number or the average of the k smallest negative numbers.

Array contains large positive and negative numbers, potential for overflow

How to Handle:

Use double precision floating-point numbers to calculate sums and averages to avoid integer overflow.

Array contains all zeros

How to Handle:

The maximum average subarray will be 0.

k is equal to the array size

How to Handle:

Return the average of all elements in the array.

Floating-point precision issues during binary search

How to Handle:

Use a small epsilon value for comparing doubles to handle potential floating-point precision errors.