Maximum Subarray Min-Product

Medium

Asked by:

27 views

Topics:

ArraysStacks

The min-product of an array is equal to the minimum value in the array multiplied by the array's sum.

For example, the array [3,2,5] (minimum value is 2) has a min-product of 2 * (3+2+5) = 2 * 10 = 20.

Given an array of integers nums, return the maximum min-product of any non-empty subarray of nums. Since the answer may be large, return it modulo 10⁹ + 7.

Note that the min-product should be maximized before performing the modulo operation. Testcases are generated such that the maximum min-product without modulo will fit in a 64-bit signed integer.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1,2,3,2]
Output: 14
Explanation: The maximum min-product is achieved with the subarray [2,3,2] (minimum value is 2).
2 * (2+3+2) = 2 * 7 = 14.

Example 2:

Input: nums = [2,3,3,1,2]
Output: 18
Explanation: The maximum min-product is achieved with the subarray [3,3] (minimum value is 3).
3 * (3+3) = 3 * 6 = 18.

Example 3:

Input: nums = [3,1,5,6,4,2]
Output: 60
Explanation: The maximum min-product is achieved with the subarray [5,6,4] (minimum value is 4).
4 * (5+6+4) = 4 * 15 = 60.

Constraints:

1 <= nums.length <= 10⁵
1 <= 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 within the input array? Can I expect negative numbers, zeros, or only positive integers?
What should I return if the input array is empty or null?
Could you define more precisely what is considered a 'subarray'? Is it a contiguous section of the array?
If there are multiple subarrays with the same maximum min-product, is it acceptable to return any one of them?
What is the maximum size of the input array, and should I be concerned about integer overflow when calculating the product?

Brute Force Solution

Approach

The brute force method is like trying every single possible option to find the best one. In this problem, we're trying to find a group of numbers that gives us the highest score when we multiply the smallest number in the group by the sum of all the numbers in that group.

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

First, consider every possible group of consecutive numbers, starting with groups of just one number.
Then, look at groups of two consecutive numbers, then three, and so on, until you've covered all possible group sizes.
For each group, find the smallest number and add up all the numbers in that group.
Multiply the smallest number by the sum of all the numbers in the group. This is the 'score' for that group.
Keep track of the highest 'score' you've found so far.
After you've checked every possible group, the highest score you've kept track of is your answer.

Code Implementation

def max_subarray_min_product_brute_force(numbers):
    max_product = 0

    # Iterate through all possible subarray starting positions
    for start_index in range(len(numbers)):

        # Iterate through all possible subarray ending positions
        for end_index in range(start_index, len(numbers)):
            current_subarray = numbers[start_index:end_index + 1]

            # Finding the minimum value is necessary for min-product
            minimum_value = min(current_subarray)

            subarray_sum = sum(current_subarray)

            current_product = minimum_value * subarray_sum

            # Track the largest min-product found
            max_product = max(max_product, current_product)

    return max_product

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates through all possible subarrays of the input array of size n. For each starting index, there's a loop to consider all possible ending indices, leading to a nested loop structure. Inside the inner loop, for each subarray, the minimum element and the sum of elements need to be computed which requires an additional loop that iterates over the current subarray. Therefore, the overall time complexity is O(n³).

Space Complexity

O(1) – The brute force approach described only uses a few variables to store the current subarray's minimum value, sum, and the overall maximum product encountered so far. These variables consume constant space regardless of the size of the input array, denoted as N. No auxiliary data structures like lists or hash maps are created to store intermediate results. Therefore, the algorithm's auxiliary space complexity is O(1).

Optimal Solution

Approach

The challenge is to find a segment of numbers where the smallest number in that segment, multiplied by the sum of all the numbers in that segment, is as large as possible. To solve this efficiently, we cleverly track ranges where each number is the minimum, and calculate the product only for those ranges.

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

For each number, find the largest possible range of numbers on either side of it, where that number is the smallest number in that range.
Calculate the sum of all the numbers within each of these ranges.
Multiply each number by the sum of its corresponding range to get the 'min-product' for that range.
Keep track of the largest min-product found so far.
At the end, the largest min-product you've tracked is the answer.

Code Implementation

def max_subarray_min_product(numbers):
    length = len(numbers)
    maximum_min_product = 0
    prefix_sums = [0] * (length + 1)
    for i in range(length): 
        prefix_sums[i+1] = prefix_sums[i] + numbers[i]

    # Iterate through each number as a potential minimum
    for i in range(length):
        left_index = i
        while left_index > 0 and numbers[left_index - 1] >= numbers[i]:
            left_index -= 1

        right_index = i
        while right_index < length - 1 and numbers[right_index + 1] >= numbers[i]:
            right_index += 1

        # Calculate subarray sum based on determined indices.
        sub_array_sum = prefix_sums[right_index + 1] - prefix_sums[left_index]
        current_min_product = numbers[i] * sub_array_sum

        # Keep track of the largest min-product
        maximum_min_product = max(maximum_min_product, current_min_product)

    return maximum_min_product

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each of the n numbers in the input array once to determine the largest possible range where that number is the minimum. Finding the left and right boundaries of these ranges can be done in O(n) time using techniques like a monotonic stack. Calculating the sum of the numbers within each range also takes O(n) time using prefix sums. Therefore, the overall time complexity is dominated by the initial iteration through the array and the monotonic stack operations, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm uses auxiliary space to store prefix sums and two stacks to determine the ranges for each number. The prefix sum array requires O(N) space, and each stack can potentially hold all indices in the worst case, also requiring O(N) space. Therefore, the overall auxiliary space used is proportional to the input size N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately as there is no subarray.
Array with a single element	Return the square of the element as it's both the minimum and the subarray.
Array with all identical positive values	The entire array multiplied by the common value will be the maximum min-product.
Array with all identical negative values	The single largest (least negative) value squared will be the maximum min-product since the negative product decreases as the window expands.
Array with only zeros	Return 0 as the min-product will always be zero.
Array with large positive numbers that could lead to integer overflow during multiplication	Use long data type to store intermediate products to prevent overflow.
Array with a single very large positive number and the rest small negative numbers.	The min product should be the large number squared, as any subarray with the negative values will result in a small product.
Maximum-sized array (constraints specify the maximum size)	Ensure the prefix sum array and other auxiliary data structures have sufficient memory allocated, and verify that the algorithm's time complexity is within acceptable limits (e.g., O(n)).

Empty input array

How to Handle:

Return 0 immediately as there is no subarray.

Array with a single element

How to Handle:

Return the square of the element as it's both the minimum and the subarray.

Array with all identical positive values

How to Handle:

The entire array multiplied by the common value will be the maximum min-product.

Array with all identical negative values

How to Handle:

The single largest (least negative) value squared will be the maximum min-product since the negative product decreases as the window expands.

Array with only zeros

How to Handle:

Return 0 as the min-product will always be zero.

Array with large positive numbers that could lead to integer overflow during multiplication

How to Handle:

Use long data type to store intermediate products to prevent overflow.

Array with a single very large positive number and the rest small negative numbers.

How to Handle:

The min product should be the large number squared, as any subarray with the negative values will result in a small product.

Maximum-sized array (constraints specify the maximum size)

How to Handle:

Ensure the prefix sum array and other auxiliary data structures have sufficient memory allocated, and verify that the algorithm's time complexity is within acceptable limits (e.g., O(n)).