Introduction

The Sum of Subarray Minimums problem involves finding:

sum of minimum elements from all possible subarrays

The task is to:

  • generate contribution of every element
  • calculate how many subarrays use it as minimum
  • return total sum

Example:

Input:arr = [3,1,2,4]

Output:
17

Explanation:

Subarrays:[3] -> 3
[1] -> 1
[2] -> 2
[4] -> 4
[3,1] -> 1
[1,2] -> 1
[2,4] -> 2
[3,1,2] -> 1
[1,2,4] -> 1
[3,1,2,4] -> 1

Total:
17

This problem is one of the most important applications of:

Monotonic Stack

Constraints

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

Approach 1 : Brute Force (Generate All Subarrays)

Explanations:

Explanation:

The idea is:

  • generate every subarray
  • find minimum element
  • add minimum to answer

Steps:

  1. Generate all subarrays.
  2. Find minimum of each subarray.
  3. Add to total sum.

This approach becomes inefficient because:

  • huge number of subarrays
  • repeated minimum calculations

So monotonic stack solution is preferred.

Dry Run

Input:[3,1,2,4]

Subarrays:
[3] -> 3
[3,1] -> 1
[3,1,2] -> 1
[3,1,2,4] -> 1

Continue for all subarrays...

Final Sum:
17

Practice :

Complexity Analysis :

Time Complexity:- O(n²)Explanation :
All subarrays are generated.

Space Complexity:- O(1)
Explanation :
No extra space is used.

Approach 2 : Optimal Solution(Using Monotonic Stack)

Explanations:

Explanation:

This is the most optimized and interview-preferred solution.

The idea is:

  • find Previous Smaller Element
  • find Next Smaller Element
  • calculate contribution of every element

Formula:

Contribution = arr[i]*leftCount*rightCount

This efficiently computes total minimum sum.

Dry Run

Input:[3,1,2,4]

Element:
1

Left choices:
2

Right choices:
3

Contribution:
1 * 2 * 3 = 6

Continue for all elements...

Final Sum:
17

Practice :

Complexity Analysis :

Time Complexity:- O(n)Explanation :
Each element is pushed and popped once.

Space Complexity:- O(n)
Explanation :
Stack and helper arrays are used.

Why This Problem is Important

This problem builds the foundation for:

  • Monotonic stack
  • Contribution technique
  • Subarray processing
  • Previous/Next smaller element
  • Advanced stack optimization

Real-World Applications

Subarray minimum concepts are used in:

  • Financial analytics
  • Sliding window systems
  • Data stream analysis
  • Range query optimization
  • Competitive programming

Common Beginner Mistakes

  • Incorrect smaller element conditions
  • Wrong contribution formula
  • Confusing previous and next smaller
  • Stack clearing mistakes
  • Overflow issues in multiplication

Interview Tip

Interviewers often expect:

  • monotonic stack optimization
  • contribution technique explanation
  • O(n) solution
  • previous/next smaller logic

Always explain:

  • why each element contributes independently
  • how stack helps find boundaries efficiently

Related Questions

  • Largest Rectangle in Histogram
  • Daily Temperatures
  • Next Greater Element
  • Car Fleet
  • Sum of Subarray Ranges

Final Takeaway

The Sum of Subarray Minimums problem is one of the most important advanced monotonic stack problems.

It teaches:

  • contribution technique
  • previous/next smaller logic
  • stack optimization
  • subarray processing

Understanding this problem builds a strong foundation for:

  •  advanced stack algorithms
  • range query optimization
  • interview-level monotonic stack problems.