Jobs

Interviews

Discussions

Sum of Subarray Minimums

Medium

Apple

5 views

Topics:

ArraysStacks

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^9 + 7.

For example:

arr = [3,1,2,4] should return 17 because the subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. The minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. The sum is 17.
arr = [11,81,94,43,3] should return 444

Explain how you would approach this problem, and write code.

Constraints:

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

Sum of Subarray Minimums

Medium

Apple

5 views

Topics:

ArraysStacks

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^9 + 7.

For example:

arr = [3,1,2,4] should return 17 because the subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. The minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. The sum is 17.
arr = [11,81,94,43,3] should return 444

Explain how you would approach this problem, and write code.

Constraints:

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

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? Can they be negative, zero, or only positive?
What is the maximum size of the input array?
Are there any duplicate values within the input array, and if so, how should they be handled when calculating the sum of subarray minimums?
Should the result be returned modulo a specific number to prevent integer overflow? If so, what is that number?
Could you provide a clarifying example with a small array to illustrate the expected calculation and output?

Brute Force Solution

Approach

The goal is to find the sum of the smallest number in every possible group of consecutive numbers in a list. The brute force method looks at every single possible group of numbers. Then it finds the smallest number in that group.

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

First, consider every possible group of consecutive numbers that starts at the beginning of the list. This means starting with a group of just the first number, then a group of the first two numbers, then the first three, and so on.
For each of these groups, find the smallest number.
Next, consider every possible group of consecutive numbers that starts at the second number in the list. Again, consider groups of increasing size.
Find the smallest number in each of those groups too.
Keep doing this, moving the starting point one number at a time down the list, always finding the smallest number in each group that starts at that point.
Once you have found the smallest number in every single possible group, add all of those smallest numbers together. The result is the final answer.

Code Implementation

def sum_of_subarray_minimums_brute_force(numbers):
    total_sum_of_minimums = 0
    list_length = len(numbers)

    for starting_index in range(list_length):
        # Iterate through all possible starting positions for subarrays

        for ending_index in range(starting_index, list_length):
            # Iterate through all possible ending positions for subarrays
            # Extract the current subarray based on the start and end indices
            current_subarray = numbers[starting_index : ending_index + 1]

            minimum_value_in_subarray = current_subarray[0]
            # Assume the first element is the minimum to start

            for number in current_subarray:
                if number < minimum_value_in_subarray:
                    minimum_value_in_subarray = number

            # Add the minimum of the current subarray to the total sum
            total_sum_of_minimums += minimum_value_in_subarray

    return total_sum_of_minimums

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates through each of the n elements of the array, defining the starting point of the subarray. The inner loop expands the subarray from the starting point to the end of the array. Inside the inner loop, we find the minimum element of the subarray. Therefore, for each starting point, the number of operations increases linearly with the size of the array. This results in approximately n * n/2 operations, which simplifies to a time complexity of O(n²).

Space Complexity

O(1) – The described brute force approach iterates through subarrays and calculates the minimum for each subarray. It doesn't appear to use any additional data structures that scale with the input size N (the number of elements in the list). The operations involve only basic variable assignments and comparisons within the loops. Therefore, the auxiliary space complexity is constant, independent of the input size N.

Optimal Solution

Approach

The trick is to figure out, for each number in the list, how many subarrays it's the smallest number in. We use a clever approach to count these subarrays efficiently without checking every single one.

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

For each number in the list, we want to know how many smaller or equal numbers are to its left until we find a smaller number.
Similarly, we want to know how many smaller numbers are to its right until we find a smaller or equal number.
Multiply these two counts together. This tells us how many subarrays exist where our chosen number is the smallest.
Multiply that result by the number itself. This gives the sum of the contributions of that number to all the subarrays where it's the minimum.
Do this for every number in the list.
Finally, add up all the individual sums to get the total sum of subarray minimums.

Code Implementation

def sub_array_minimums(array_of_numbers):
    total_sum = 0
    array_length = len(array_of_numbers)
    modulo = 10**9 + 7

    for i in range(array_length):
        # Find numbers to the left that are >= current number
        left_count = 1
        left_index = i - 1

        while left_index >= 0 and array_of_numbers[left_index] >= array_of_numbers[i]:
            left_count += 1
            left_index -= 1

        # Find numbers to the right that are > current number
        right_count = 1
        right_index = i + 1

        while right_index < array_length and array_of_numbers[right_index] > array_of_numbers[i]:
            right_count += 1
            right_index += 1

        # Crucial step: Calculate contribution of current element
        total_sum = (total_sum + array_of_numbers[i] * left_count * right_count) % modulo

    return total_sum

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through each number in the input array of size n. For each number, it finds the count of smaller or equal numbers to its left and smaller numbers to its right. These counts are found using stacks, which effectively allow determining the boundaries in linear time for each element. Since each element is processed in O(1) time on average thanks to the stacks (each element is pushed and popped at most once), the overall time complexity is driven by the initial loop through the array, resulting in O(n) complexity.

Space Complexity

O(N) – The provided explanation describes iterating through the input array and using two stacks to determine the number of smaller or equal elements to the left and smaller elements to the right for each element. Each stack can, in the worst case, hold all N elements of the input array. Therefore, the auxiliary space used is proportional to the size of the input, N, making the space complexity O(N).

Edge Cases

Case	How to Handle
Empty input array	Return 0 as the sum of subarray minimums is zero when there are no subarrays.
Array with a single element	Return the single element itself, as it's the minimum of the only possible subarray.
Array with all identical elements	The solution should correctly calculate the number of subarrays each element is the minimum of.
Array with a descending sorted order	Each element will be the minimum of all subarrays starting at that element, requiring the solution to handle this case correctly.
Array with an ascending sorted order	The first element will always be the minimum of every possible subarray, requiring careful consideration of subarray counts.
Large array causing potential integer overflow in the sum	Use modulo arithmetic with a sufficiently large prime number during summation to prevent overflow.
Array containing negative numbers	The algorithm should correctly handle negative numbers as potential minimums within subarrays.
Array with very large numbers, approaching the maximum integer value	Ensure intermediate calculations involving these numbers do not cause integer overflow before applying the modulo operator.

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? Can they be negative, zero, or only positive?
What is the maximum size of the input array?
Are there any duplicate values within the input array, and if so, how should they be handled when calculating the sum of subarray minimums?
Should the result be returned modulo a specific number to prevent integer overflow? If so, what is that number?
Could you provide a clarifying example with a small array to illustrate the expected calculation and output?

Brute Force Solution

Approach

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

First, consider every possible group of consecutive numbers that starts at the beginning of the list. This means starting with a group of just the first number, then a group of the first two numbers, then the first three, and so on.
For each of these groups, find the smallest number.
Next, consider every possible group of consecutive numbers that starts at the second number in the list. Again, consider groups of increasing size.
Find the smallest number in each of those groups too.
Keep doing this, moving the starting point one number at a time down the list, always finding the smallest number in each group that starts at that point.
Once you have found the smallest number in every single possible group, add all of those smallest numbers together. The result is the final answer.

Code Implementation

def sum_of_subarray_minimums_brute_force(numbers):
    total_sum_of_minimums = 0
    list_length = len(numbers)

    for starting_index in range(list_length):
        # Iterate through all possible starting positions for subarrays

        for ending_index in range(starting_index, list_length):
            # Iterate through all possible ending positions for subarrays
            # Extract the current subarray based on the start and end indices
            current_subarray = numbers[starting_index : ending_index + 1]

            minimum_value_in_subarray = current_subarray[0]
            # Assume the first element is the minimum to start

            for number in current_subarray:
                if number < minimum_value_in_subarray:
                    minimum_value_in_subarray = number

            # Add the minimum of the current subarray to the total sum
            total_sum_of_minimums += minimum_value_in_subarray

    return total_sum_of_minimums

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

For each number in the list, we want to know how many smaller or equal numbers are to its left until we find a smaller number.
Similarly, we want to know how many smaller numbers are to its right until we find a smaller or equal number.
Multiply these two counts together. This tells us how many subarrays exist where our chosen number is the smallest.
Multiply that result by the number itself. This gives the sum of the contributions of that number to all the subarrays where it's the minimum.
Do this for every number in the list.
Finally, add up all the individual sums to get the total sum of subarray minimums.

Code Implementation

def sub_array_minimums(array_of_numbers):
    total_sum = 0
    array_length = len(array_of_numbers)
    modulo = 10**9 + 7

    for i in range(array_length):
        # Find numbers to the left that are >= current number
        left_count = 1
        left_index = i - 1

        while left_index >= 0 and array_of_numbers[left_index] >= array_of_numbers[i]:
            left_count += 1
            left_index -= 1

        # Find numbers to the right that are > current number
        right_count = 1
        right_index = i + 1

        while right_index < array_length and array_of_numbers[right_index] > array_of_numbers[i]:
            right_count += 1
            right_index += 1

        # Crucial step: Calculate contribution of current element
        total_sum = (total_sum + array_of_numbers[i] * left_count * right_count) % modulo

    return total_sum

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 as the sum of subarray minimums is zero when there are no subarrays.
Array with a single element	Return the single element itself, as it's the minimum of the only possible subarray.
Array with all identical elements	The solution should correctly calculate the number of subarrays each element is the minimum of.
Array with a descending sorted order	Each element will be the minimum of all subarrays starting at that element, requiring the solution to handle this case correctly.
Array with an ascending sorted order	The first element will always be the minimum of every possible subarray, requiring careful consideration of subarray counts.
Large array causing potential integer overflow in the sum	Use modulo arithmetic with a sufficiently large prime number during summation to prevent overflow.
Array containing negative numbers	The algorithm should correctly handle negative numbers as potential minimums within subarrays.
Array with very large numbers, approaching the maximum integer value	Ensure intermediate calculations involving these numbers do not cause integer overflow before applying the modulo operator.