Jobs

Interviews

Discussions

Maximum Score of a Good Subarray

Hard

Google

1 view

Topics:

ArraysTwo Pointers

You are given an array of integers nums (0-indexed) and an integer k. The score of a subarray (i, j) is defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1). A good subarray is a subarray where i <= k <= j. Return the maximum possible score of a good subarray.

For example:

nums = [1,4,3,7,4,5], k = 3. The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15.
nums = [5,5,4,5,4,1,1,1], k = 0. The optimal subarray is (0, 4) with a score of min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20.

Could you provide a solution to find the maximum possible score of a good subarray?

Maximum Score of a Good Subarray

Hard

Google

1 view

Topics:

ArraysTwo Pointers

For example:

nums = [1,4,3,7,4,5], k = 3. The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15.
nums = [5,5,4,5,4,1,1,1], k = 0. The optimal subarray is (0, 4) with a score of min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20.

Could you provide a solution to find the maximum possible score of a good subarray?

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 are the possible ranges for the numbers in the input array `nums` and for the input integer `k`?
Can the input array `nums` be empty, and what should I return if it is?
What defines a 'good' subarray precisely? Is it that `k` is inside the subarray indices, or that `nums[k]` is actually the element in the subarray?
If there are multiple good subarrays with the same maximum score, can I return any one of them, or is there a specific one I need to return based on length or index?
Can the array contain duplicate values, and how do they affect the calculation of the score?

Brute Force Solution

Approach

The brute force approach to finding the maximum score of a good subarray involves checking every possible subarray. We consider each possible starting point and ending point within the given numbers. We then validate if this subarray is considered 'good' and calculate the score.

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

Start by considering the first number as the start of a potential subarray and the same first number as the end.
Check if this single-number subarray is a 'good' subarray based on the given definition. If so, calculate its score and remember it.
Next, expand the subarray to include the first two numbers, with the first number still as the start and the second number as the end.
Again, check if this two-number subarray is 'good', calculate its score, and compare it to the previously remembered score. Keep the higher score.
Continue expanding the subarray from the start by one number at a time, checking if it's 'good', calculating the score, and comparing until you've reached the end of the numbers.
Now, move to the second number and treat it as the start of a new set of subarrays. Repeat the expanding and checking process as before.
Keep doing this, moving the starting point one number at a time through all of the numbers, until you've started a subarray from every number.
At the end, you will have checked every single possible subarray. The highest score found during this process is the maximum score of a 'good' subarray.

Code Implementation

def maximum_score_of_good_subarray_brute_force(numbers, lower_bound):
    maximum_score = 0

    # Iterate through all possible starting points
    for start_index in range(len(numbers)):
        # Iterate through all possible ending points for each starting point
        for end_index in range(start_index, len(numbers)):
            current_subarray = numbers[start_index:end_index + 1]

            # Check if the subarray is a 'good' subarray
            is_good = all(number >= lower_bound for number in current_subarray)

            if is_good:
                # Calculate score only if subarray is 'good'
                current_score = sum(current_subarray)

                # Update maximum score if necessary
                maximum_score = max(maximum_score, current_score)

    return maximum_score

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible subarrays of the input array of size n. The outer loop selects the starting index of the subarray, and the inner loop selects the ending index. In the worst case, for each of the n starting positions, the algorithm considers all remaining n elements as possible ending positions, resulting in nested loops. This leads to approximately n * (n+1) / 2 operations, which simplifies to O(n²).

Space Complexity

O(1) – The brute force approach described checks every possible subarray using nested loops. While it iterates through all possible subarrays, it doesn't create any auxiliary data structures to store the subarrays themselves or any intermediate results. The algorithm only needs to store a few variables, such as the start and end indices of the current subarray and the maximum score found so far, all of which require constant space, irrespective of the input size N (the number of elements in the input array). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The key to maximizing the score is to expand outwards from the given starting point. We maintain the best possible score as we expand, making sure the subarray we're looking at is always 'good'.

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

Start at the given position in the list of numbers.
Consider this single number as a 'good' subarray to begin with.
Expand outwards from the starting position in both directions (left and right).
At each step, check if the new subarray is still 'good' (meaning the smallest number in the subarray is at least the number at the starting position).
If the subarray is still 'good', calculate its score by multiplying the smallest number in the subarray by the length of the subarray.
Keep track of the highest score you've found so far.
Continue expanding the subarray outwards until it's no longer 'good' in either direction.
Return the highest score you found while expanding.

Code Implementation

def maximum_score_of_a_good_subarray(numbers, starting_index):
    highest_score = numbers[starting_index]
    left_index = starting_index
    right_index = starting_index
    minimum_value = numbers[starting_index]

    while left_index > 0 or right_index < len(numbers) - 1:
        # Expand in the direction with the larger value
        if left_index == 0:
            right_index += 1
        elif right_index == len(numbers) - 1:
            left_index -= 1
        elif numbers[left_index - 1] < numbers[right_index + 1]:
            right_index += 1
        else:
            left_index -= 1

        # Maintain the smallest value in the current good subarray
        minimum_value = min(minimum_value, numbers[left_index], numbers[right_index])

        # Calculate the score of the current good subarray
        current_score = minimum_value * (right_index - left_index + 1)

        # Update the highest score if necessary
        highest_score = max(highest_score, current_score)

    return highest_score

Big(O) Analysis

Time Complexity

O(n) – The algorithm expands outwards from the given index. In the worst case, it expands to the entire array in both directions, left and right, from the starting index 'k'. Since each element is visited at most a constant number of times (once while expanding left and once while expanding right), the time complexity is directly proportional to the size of the input array 'n'. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It maintains a few variables such as the current left and right boundaries of the subarray being considered, and the maximum score found so far. The space needed for these variables does not depend on the input size N (the length of the input list of numbers). Therefore the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty nums array	Return 0, as there are no subarrays to consider.
nums array with one element	Return the single element's value as the maximum score with k=0.
k is at the beginning or end of the array	Ensure the sliding window expands correctly from these boundary indices.
All elements in nums are the same	The minimum value will be that element, so the problem reduces to finding the largest subarray containing 'k'.
All elements in nums are very large positive numbers causing potential integer overflow	Use a larger data type like long to store the product and sum to avoid overflow.
nums contains negative numbers and zeros	Handle zero values correctly in calculating the minimum value and ensure the multiplication does not result in unintended negative minimums.
k is in the middle of a monotonically increasing or decreasing sequence	The window will always expand at least to include k, properly handling the monotonic nature of sequences.
Large array size with k near the beginning of the array	The while loops should still terminate correctly, as the condition depends on i >= 0 and j < n not array size.

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 are the possible ranges for the numbers in the input array `nums` and for the input integer `k`?
Can the input array `nums` be empty, and what should I return if it is?
What defines a 'good' subarray precisely? Is it that `k` is inside the subarray indices, or that `nums[k]` is actually the element in the subarray?
If there are multiple good subarrays with the same maximum score, can I return any one of them, or is there a specific one I need to return based on length or index?
Can the array contain duplicate values, and how do they affect the calculation of the score?

Brute Force Solution

Approach

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

Start by considering the first number as the start of a potential subarray and the same first number as the end.
Check if this single-number subarray is a 'good' subarray based on the given definition. If so, calculate its score and remember it.
Next, expand the subarray to include the first two numbers, with the first number still as the start and the second number as the end.
Again, check if this two-number subarray is 'good', calculate its score, and compare it to the previously remembered score. Keep the higher score.
Continue expanding the subarray from the start by one number at a time, checking if it's 'good', calculating the score, and comparing until you've reached the end of the numbers.
Now, move to the second number and treat it as the start of a new set of subarrays. Repeat the expanding and checking process as before.
Keep doing this, moving the starting point one number at a time through all of the numbers, until you've started a subarray from every number.
At the end, you will have checked every single possible subarray. The highest score found during this process is the maximum score of a 'good' subarray.

Code Implementation

def maximum_score_of_good_subarray_brute_force(numbers, lower_bound):
    maximum_score = 0

    # Iterate through all possible starting points
    for start_index in range(len(numbers)):
        # Iterate through all possible ending points for each starting point
        for end_index in range(start_index, len(numbers)):
            current_subarray = numbers[start_index:end_index + 1]

            # Check if the subarray is a 'good' subarray
            is_good = all(number >= lower_bound for number in current_subarray)

            if is_good:
                # Calculate score only if subarray is 'good'
                current_score = sum(current_subarray)

                # Update maximum score if necessary
                maximum_score = max(maximum_score, current_score)

    return maximum_score

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The key to maximizing the score is to expand outwards from the given starting point. We maintain the best possible score as we expand, making sure the subarray we're looking at is always 'good'.

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

Start at the given position in the list of numbers.
Consider this single number as a 'good' subarray to begin with.
Expand outwards from the starting position in both directions (left and right).
At each step, check if the new subarray is still 'good' (meaning the smallest number in the subarray is at least the number at the starting position).
If the subarray is still 'good', calculate its score by multiplying the smallest number in the subarray by the length of the subarray.
Keep track of the highest score you've found so far.
Continue expanding the subarray outwards until it's no longer 'good' in either direction.
Return the highest score you found while expanding.

Code Implementation

def maximum_score_of_a_good_subarray(numbers, starting_index):
    highest_score = numbers[starting_index]
    left_index = starting_index
    right_index = starting_index
    minimum_value = numbers[starting_index]

    while left_index > 0 or right_index < len(numbers) - 1:
        # Expand in the direction with the larger value
        if left_index == 0:
            right_index += 1
        elif right_index == len(numbers) - 1:
            left_index -= 1
        elif numbers[left_index - 1] < numbers[right_index + 1]:
            right_index += 1
        else:
            left_index -= 1

        # Maintain the smallest value in the current good subarray
        minimum_value = min(minimum_value, numbers[left_index], numbers[right_index])

        # Calculate the score of the current good subarray
        current_score = minimum_value * (right_index - left_index + 1)

        # Update the highest score if necessary
        highest_score = max(highest_score, current_score)

    return highest_score

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty nums array	Return 0, as there are no subarrays to consider.
nums array with one element	Return the single element's value as the maximum score with k=0.
k is at the beginning or end of the array	Ensure the sliding window expands correctly from these boundary indices.
All elements in nums are the same	The minimum value will be that element, so the problem reduces to finding the largest subarray containing 'k'.
All elements in nums are very large positive numbers causing potential integer overflow	Use a larger data type like long to store the product and sum to avoid overflow.
nums contains negative numbers and zeros	Handle zero values correctly in calculating the minimum value and ensure the multiplication does not result in unintended negative minimums.
k is in the middle of a monotonically increasing or decreasing sequence	The window will always expand at least to include k, properly handling the monotonic nature of sequences.
Large array size with k near the beginning of the array	The while loops should still terminate correctly, as the condition depends on i >= 0 and j < n not array size.