Jobs

Interviews

Discussions

Sum of Subarray Minimums

Medium

Asked by:

More companies

114 views

Topics:

ArraysStacksDynamic Programming

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 10⁹ + 7.

Example 1:

Input: arr = [3,1,2,4]
Output: 17
Explanation: 
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.

Example 2:

Input: arr = [11,81,94,43,3]
Output: 444

Constraints:

1 <= arr.length <= 3 * 10⁴
1 <= arr[i] <= 3 * 10⁴

Try coding it in LeetCode

Sum of Subarray Minimums

Medium

Asked by:

More companies

114 views

Topics:

ArraysStacksDynamic Programming

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 10⁹ + 7.

Example 1:

Input: arr = [3,1,2,4]
Output: 17
Explanation: 
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.

Example 2:

Input: arr = [11,81,94,43,3]
Output: 444

Constraints:

1 <= arr.length <= 3 * 10⁴
1 <= arr[i] <= 3 * 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 are the constraints on the size of the input array `arr` and the range of values within `arr`?
Can the input array `arr` contain negative numbers, zeros, or null values?
Are there any specific edge cases or boundary conditions I should be aware of, such as an empty array?
Could you clarify the expected behavior if the sum of minimums exceeds the maximum value that can be stored before applying the modulo operator?
Are there duplicate numbers in the array, and if so, how should they be handled when determining the minimum of a subarray?

Brute Force Solution

Approach

The brute force approach to finding the sum of subarray minimums involves looking at every possible group of numbers within the larger set. For each of these groups, we'll find the smallest number and then add it to our running total. Finally, after checking every group, we'll have our answer.

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

Consider every possible group of numbers we can form from the original set. A group could be just one number, two adjacent numbers, three adjacent numbers, and so on, up to the entire set of numbers.
For each group we consider, find the smallest number within that group.
Add this smallest number to a running total that starts at zero.
Repeat steps two and three for every possible group we identified in step one.
The final running total will be the sum of the minimums of all possible groups.

Code Implementation

def sum_subarray_minimums_brute_force(array):
    total_sum = 0
    array_length = len(array)

    # Iterate through all possible starting positions of subarrays
    for start_index in range(array_length):

        # Iterate through all possible ending positions of subarrays
        for end_index in range(start_index, array_length):
            minimum_value = array[start_index]

            # Find the minimum element within the current subarray
            for current_index in range(start_index, end_index + 1):
                if array[current_index] < minimum_value:
                    minimum_value = array[current_index]

            # Add the minimum of the subarray to the total sum
            total_sum += minimum_value

    return total_sum

Big(O) Analysis

Time Complexity

O(n³) – The brute force approach iterates through all possible subarrays. There are roughly n subarrays starting at each of the n indices of the input array. Finding the minimum element within each of these subarrays requires iterating through the subarray in O(n) time. Since we are finding the minimum of approximately n^2 subarrays and finding each of those minimums takes O(n) time, the total time complexity is O(n * n * n), which simplifies to O(n³).

Space Complexity

O(1) – The brute force approach described only uses a running total variable to accumulate the sum of minimums. It iterates through all possible subarrays but doesn't create any auxiliary data structures to store these subarrays or intermediate results. The space used remains constant regardless of the input array's size, N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The efficient way to find the sum of the minimum values of all subarrays avoids recalculating the minimum for each subarray. It cleverly uses a 'stack' to keep track of relevant elements and their contribution to the final sum, significantly reducing redundant work.

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

Imagine each number in the sequence as a potential minimum value for some subarrays.
For each number, figure out how many subarrays it will actually be the smallest number in.
To do this, find the nearest smaller numbers to the left and to the right of the current number.
The number of subarrays where the current number is the minimum is determined by the distances to these nearest smaller numbers.
Specifically, it is the product of the distance to the left and the distance to the right.
Multiply the current number by the number of subarrays it is the minimum for, to calculate its total contribution to the final sum.
Repeat for every number in the sequence.
Add up all of these contributions to get the final answer. This takes care of all subarrays without needing to look at each one individually.

Code Implementation

def sum_subarray_minimums(arr):
    length_of_array = len(arr)
    modulo = 10**9 + 7
    stack = []
    sum_of_minimums = 0

    # Find previous less element for each element.
    previous_less_element = [0] * length_of_array
    for i in range(length_of_array):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        previous_less_element[i] = stack[-1] if stack else -1
        stack.append(i)

    stack = []

    # Find next less element for each element.
    next_less_element = [0] * length_of_array
    for i in range(length_of_array - 1, -1, -1):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        next_less_element[i] = stack[-1] if stack else length_of_array
        stack.append(i)

    # Calculate the contribution of each element as minimum.
    for i in range(length_of_array):
        left_distance = i - previous_less_element[i]

        # Distance to the next smaller element.
        right_distance = next_less_element[i] - i

        sum_of_minimums += arr[i] * left_distance * right_distance
        sum_of_minimums %= modulo

    return sum_of_minimums

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once to find the nearest smaller elements to the left and once to find the nearest smaller elements to the right using a stack. The stack operations (push and pop) take constant time on average. Therefore, the overall time complexity is dominated by the single iteration through the array, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm uses a stack to find the nearest smaller elements to the left and right for each number in the input array. In the worst-case scenario, the stack could contain all N elements of the input array if the input array is sorted in descending order. Therefore, the auxiliary space used by the stack is proportional to the input size N. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input array	Return 0 as there are no subarrays.
Array with a single element	Return the element itself, as it's the only subarray and its minimum.
Array with all identical elements	The minimum of each subarray is the same element, so calculate number of subarrays correctly (n(n+1))/2 element and return modulo.
Array with very large numbers that could lead to integer overflow when summing	Apply the modulo operation (10^9 + 7) after each addition to prevent integer overflow.
Array containing negative numbers	The algorithm should handle negative numbers correctly since it compares values to find the minimum.
Array with a mix of large positive and large negative numbers	Ensure the modulo operation handles negative results correctly (e.g., by adding the modulo value if the result is negative).
Large input array size (performance)	Optimized algorithms like using a stack to determine the left and right boundaries for each element being the minimum within a range are needed for efficiency.
Array with zeros	Zeros should be handled correctly as they could be the minimum in several subarrays.

Empty input array

How to Handle:

Return 0 as there are no subarrays.

Array with a single element

How to Handle:

Return the element itself, as it's the only subarray and its minimum.

Array with all identical elements

How to Handle:

The minimum of each subarray is the same element, so calculate number of subarrays correctly (n*(n+1))/2 * element and return modulo.

Array with very large numbers that could lead to integer overflow when summing

How to Handle:

Apply the modulo operation (10^9 + 7) after each addition to prevent integer overflow.

Array containing negative numbers

How to Handle:

The algorithm should handle negative numbers correctly since it compares values to find the minimum.

Array with a mix of large positive and large negative numbers

How to Handle:

Ensure the modulo operation handles negative results correctly (e.g., by adding the modulo value if the result is negative).

Large input array size (performance)

How to Handle:

Optimized algorithms like using a stack to determine the left and right boundaries for each element being the minimum within a range are needed for efficiency.

Array with zeros

How to Handle:

Zeros should be handled correctly as they could be the minimum in several subarrays.

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 constraints on the size of the input array `arr` and the range of values within `arr`?
Can the input array `arr` contain negative numbers, zeros, or null values?
Are there any specific edge cases or boundary conditions I should be aware of, such as an empty array?
Could you clarify the expected behavior if the sum of minimums exceeds the maximum value that can be stored before applying the modulo operator?
Are there duplicate numbers in the array, and if so, how should they be handled when determining the minimum of a subarray?

Brute Force Solution

Approach

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

Consider every possible group of numbers we can form from the original set. A group could be just one number, two adjacent numbers, three adjacent numbers, and so on, up to the entire set of numbers.
For each group we consider, find the smallest number within that group.
Add this smallest number to a running total that starts at zero.
Repeat steps two and three for every possible group we identified in step one.
The final running total will be the sum of the minimums of all possible groups.

Code Implementation

def sum_subarray_minimums_brute_force(array):
    total_sum = 0
    array_length = len(array)

    # Iterate through all possible starting positions of subarrays
    for start_index in range(array_length):

        # Iterate through all possible ending positions of subarrays
        for end_index in range(start_index, array_length):
            minimum_value = array[start_index]

            # Find the minimum element within the current subarray
            for current_index in range(start_index, end_index + 1):
                if array[current_index] < minimum_value:
                    minimum_value = array[current_index]

            # Add the minimum of the subarray to the total sum
            total_sum += minimum_value

    return total_sum

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine each number in the sequence as a potential minimum value for some subarrays.
For each number, figure out how many subarrays it will actually be the smallest number in.
To do this, find the nearest smaller numbers to the left and to the right of the current number.
The number of subarrays where the current number is the minimum is determined by the distances to these nearest smaller numbers.
Specifically, it is the product of the distance to the left and the distance to the right.
Multiply the current number by the number of subarrays it is the minimum for, to calculate its total contribution to the final sum.
Repeat for every number in the sequence.
Add up all of these contributions to get the final answer. This takes care of all subarrays without needing to look at each one individually.

Code Implementation

def sum_subarray_minimums(arr):
    length_of_array = len(arr)
    modulo = 10**9 + 7
    stack = []
    sum_of_minimums = 0

    # Find previous less element for each element.
    previous_less_element = [0] * length_of_array
    for i in range(length_of_array):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        previous_less_element[i] = stack[-1] if stack else -1
        stack.append(i)

    stack = []

    # Find next less element for each element.
    next_less_element = [0] * length_of_array
    for i in range(length_of_array - 1, -1, -1):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        next_less_element[i] = stack[-1] if stack else length_of_array
        stack.append(i)

    # Calculate the contribution of each element as minimum.
    for i in range(length_of_array):
        left_distance = i - previous_less_element[i]

        # Distance to the next smaller element.
        right_distance = next_less_element[i] - i

        sum_of_minimums += arr[i] * left_distance * right_distance
        sum_of_minimums %= modulo

    return sum_of_minimums

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 as there are no subarrays.
Array with a single element	Return the element itself, as it's the only subarray and its minimum.
Array with all identical elements	The minimum of each subarray is the same element, so calculate number of subarrays correctly (n(n+1))/2 element and return modulo.
Array with very large numbers that could lead to integer overflow when summing	Apply the modulo operation (10^9 + 7) after each addition to prevent integer overflow.
Array containing negative numbers	The algorithm should handle negative numbers correctly since it compares values to find the minimum.
Array with a mix of large positive and large negative numbers	Ensure the modulo operation handles negative results correctly (e.g., by adding the modulo value if the result is negative).
Large input array size (performance)	Optimized algorithms like using a stack to determine the left and right boundaries for each element being the minimum within a range are needed for efficiency.
Array with zeros	Zeros should be handled correctly as they could be the minimum in several subarrays.

Empty input array

How to Handle:

Return 0 as there are no subarrays.

Array with a single element

How to Handle:

Return the element itself, as it's the only subarray and its minimum.

Array with all identical elements

How to Handle:

The minimum of each subarray is the same element, so calculate number of subarrays correctly (n*(n+1))/2 * element and return modulo.

Array with very large numbers that could lead to integer overflow when summing

How to Handle:

Apply the modulo operation (10^9 + 7) after each addition to prevent integer overflow.

Array containing negative numbers

How to Handle:

The algorithm should handle negative numbers correctly since it compares values to find the minimum.

Array with a mix of large positive and large negative numbers

How to Handle:

Ensure the modulo operation handles negative results correctly (e.g., by adding the modulo value if the result is negative).

Large input array size (performance)

How to Handle:

Optimized algorithms like using a stack to determine the left and right boundaries for each element being the minimum within a range are needed for efficiency.

Array with zeros

How to Handle:

Zeros should be handled correctly as they could be the minimum in several subarrays.