What is the time complexity of Sum of Subarray Minimums?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Sum of Subarray Minimums?

This problem uses Array, Dynamic Programming, Stack, Monotonic Stack. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Sum of Subarray Minimums?

Insight 1: The naive approach of generating all subarrays and finding their minimums would result in O(n^2) time complexity, which could be too slow for the given constraints. We need a more efficient approach. Insight 2: The key insight is to use a monotonic stack to efficiently determine the left and right boundaries where each element `arr[i]` is the minimum element of subarrays. This allows calculating the number of subarrays where `arr[i]` is the minimum in O(1) time.

Which companies ask LeetCode 907. Sum of Subarray Minimums in interviews?

This problem is frequently asked at Avito, Paytm, PhonePe, Sprinklr.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Sum of Subarray Minimums - LeetCode 907 Solution

Q: How to solve Sum of Subarray Minimums?

The provided solution uses a monotonic stack to determine, for each element in the array, the range of subarrays where that element is the minimum. The algorithm iterates through the array, maintaining a stack of indices that are strictly increasing (or non-decreasing) based on their corresponding values in the array. When a new element is encountered that is smaller than or equal to the element at the top of the stack, it means that the element at the top of the stack is no longer the minimum element for subarrays that extend further. The algorithm then pops the element from the stack and calculates the number of subarrays for which the popped element is the minimum. This count is then multiplied by the value of the popped element, and the result is added to the total sum. The process repeats until the stack is empty or the current element is greater than the top of the stack. After processing the element, its index is added to the stack. A sentinel value (0) is added to the end of the array to handle the remaining elements in the stack after iterating through the entire array.

Sum of Subarray Minimums - Complete Solution Guide

Sum of Subarray Minimums is LeetCode problem 907, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 . 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 4 1 <= arr[i] <= 3 * 10 4

Detailed Explanation

The problem asks us to find the sum of the minimum elements of all contiguous subarrays within a given array `arr`. We need to consider every possible subarray, find the minimum value within each subarray, and then sum up all these minimum values. The final result should be returned modulo 10^9 + 7 to prevent integer overflow. For example, given `arr = [3, 1, 2, 4]`, 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`, and their sum is `17`. The length of the input array is between 1 and 3 * 10^4, and each element's value is between 1 and 3 * 10^4.

Solution Approach

The provided solution uses a monotonic stack to determine, for each element in the array, the range of subarrays where that element is the minimum. The algorithm iterates through the array, maintaining a stack of indices that are strictly increasing (or non-decreasing) based on their corresponding values in the array. When a new element is encountered that is smaller than or equal to the element at the top of the stack, it means that the element at the top of the stack is no longer the minimum element for subarrays that extend further. The algorithm then pops the element from the stack and calculates the number of subarrays for which the popped element is the minimum. This count is then multiplied by the value of the popped element, and the result is added to the total sum. The process repeats until the stack is empty or the current element is greater than the top of the stack. After processing the element, its index is added to the stack. A sentinel value (0) is added to the end of the array to handle the remaining elements in the stack after iterating through the entire array.

Step-by-Step Algorithm

Step 1: Initialize `MOD` to 10^9 + 7 and `total_sum` to 0. Create an empty stack to store indices.
Step 2: Iterate through the array `arr` from `i = 0` to `n` (inclusive). If `i == n`, the `current_val` is set to 0 (sentinel value); otherwise, `current_val` is `arr[i]`.
Step 3: While the stack is not empty and `current_val` is less than or equal to the element at the top of the stack (i.e., `arr[stack[-1]] >= current_val` in Python, `arr[stack.peek()] >= current_val` in Java/C++), pop the top index `mid_idx` from the stack.
Step 4: Determine the left and right boundaries for the subarrays where `arr[mid_idx]` is the minimum. `left_boundary` is the index at the top of the stack (or -1 if the stack is empty), and `right_boundary` is the current index `i`.
Step 5: Calculate the count of subarrays where `arr[mid_idx]` is the minimum: `count = (mid_idx - left_boundary) * (right_boundary - mid_idx)`.
Step 6: Update `total_sum`: `total_sum = (total_sum + arr[mid_idx] * count) % MOD`.
Step 7: Push the current index `i` onto the stack.
Step 8: After the loop completes, return `total_sum`.

Key Insights

Insight 1: The naive approach of generating all subarrays and finding their minimums would result in O(n^2) time complexity, which could be too slow for the given constraints. We need a more efficient approach.
Insight 2: The key insight is to use a monotonic stack to efficiently determine the left and right boundaries where each element `arr[i]` is the minimum element of subarrays. This allows calculating the number of subarrays where `arr[i]` is the minimum in O(1) time.
Insight 3: Using a stack to store indices helps keep track of the relative order and position of elements in the array, enabling the identification of boundaries efficiently.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Dynamic Programming, Stack, Monotonic Stack.

Companies

Asked at: Avito, Paytm, PhonePe, Sprinklr.

Sum of Subarray Minimums | LeetCode 907

Medium

Array Dynamic Programming Stack Monotonic Stack

Time: O(n)Space: O(n)

Solution Code

Available in:

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int MOD = 1000000007;
        int n = arr.length;
        long total_sum = 0;
        java.util.Stack<Integer> stack = new java.util.Stack<>(); // Store indices

        for (int i = 0; i <= n; i++) {
            int current_val = (i < n) ? arr[i] : 0;

            while (!stack.isEmpty() && (i == n || arr[stack.peek()] >= current_val)) {
                int mid_idx = stack.pop();
                int left_boundary = stack.isEmpty() ? -1 : stack.peek();
                int right_boundary = i;

                long count = (long) (mid_idx - left_boundary) * (right_boundary - mid_idx);
                total_sum = (total_sum + (long) arr[mid_idx] * count) % MOD;
            }

            stack.push(i);
        }

        return (int) total_sum;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 907: Sum of Subarray Minimums - Detailed explanation and solution approaches.

Topics

Array Dynamic Programming Stack Monotonic Stack

Companies

AvitoPaytmPhonePeSprinklr

Stats

Difficulty:Medium

Languages:4

Companies:4

Problem #:907

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Initialize `MOD` to 10^9 + 7 and `total_sum` to 0. Create an empty stack to store indices.
2
Step 2: Iterate through the array `arr` from `i = 0` to `n` (inclusive). If `i == n`, the `current_val` is set to 0 (sentinel value); otherwise, `current_val` is `arr[i]`.
3
Step 3: While the stack is not empty and `current_val` is less than or equal to the element at the top of the stack (i.e., `arr[stack[-1]] >= current_val` in Python, `arr[stack.peek()] >= current_val` in Java/C++), pop the top index `mid_idx` from the stack.
4
Step 4: Determine the left and right boundaries for the subarrays where `arr[mid_idx]` is the minimum. `left_boundary` is the index at the top of the stack (or -1 if the stack is empty), and `right_boundary` is the current index `i`.
5
Step 5: Calculate the count of subarrays where `arr[mid_idx]` is the minimum: `count = (mid_idx - left_boundary) * (right_boundary - mid_idx)`.
6
Step 6: Update `total_sum`: `total_sum = (total_sum + arr[mid_idx] * count) % MOD`.
7
Step 7: Push the current index `i` onto the stack.
8
Step 8: After the loop completes, return `total_sum`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The monotonic stack ensures each element is visited and processed a maximum of twice (pushed and popped). This characteristic gives us linear time complexity. The stack, in the worst case, may store every index, resulting in linear space complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Iterate through all possible subarrays, find the minimum of each subarray, and sum the minimums. This involves nested loops and is inefficient.

Time: O(n^2), where n is the length of the array.Space: O(1)

Trade-offs: This approach is simple to understand but is not suitable for large input sizes due to its quadratic time complexity. It is better to use the monotonic stack for a more efficient O(n) solution.

✨

Key Insights

1Insight 1: The naive approach of generating all subarrays and finding their minimums would result in O(n^2) time complexity, which could be too slow for the given constraints. We need a more efficient approach.
2Insight 2: The key insight is to use a monotonic stack to efficiently determine the left and right boundaries where each element `arr[i]` is the minimum element of subarrays. This allows calculating the number of subarrays where `arr[i]` is the minimum in O(1) time.
3Insight 3: Using a stack to store indices helps keep track of the relative order and position of elements in the array, enabling the identification of boundaries efficiently.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

Edge Cases

Edge case 1: Empty input array. The solution implicitly handles it because the loop does not execute, and 0 is returned.
Edge case 2: An array with all identical elements. The monotonic stack approach correctly calculates the contribution of each element since the condition `arr[stack.top()] >= current_val` ensures that even identical elements are processed correctly.
Edge case 3: Strictly increasing array. The stack will contain all indices until the sentinel value is added. This is handled correctly by calculating the contribution from each element on the stack.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not taking the modulo operation at each step. Integer overflow may occur if the intermediate sum exceeds the maximum representable integer value. Taking modulo at each step prevents this.

✗Common mistake 2: Incorrectly calculating the left and right boundaries for each element. It is essential to consider the elements present in the stack and their positions to determine the correct number of subarrays for which an element is the minimum.

✗Common mistake 3: Forgetting to handle the elements remaining in the stack after processing the entire array. The sentinel value ensures all elements are processed.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Analyzing stock prices to find periods where the price remains the lowest. This can be used to identify potential buying opportunities or assess market trends.

🏦Real-world scenario 2: Signal processing where we need to identify the minimum value within sliding windows of data. This is useful in noise reduction or anomaly detection.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 8, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Should I use top-down (memoization) or bottom-up (tabulation)?

Start with top-down (recursion + memoization) as it directly maps to the recursive thinking and handles only needed subproblems. Convert to bottom-up for better space efficiency and to avoid stack overflow. Bottom-up is often faster due to no recursion overhead.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Sum of Subarray Minimums"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?