Sum of Subarray Minimum Using Stack and Queue

The Sum of Subarray Minimum problem is a well-known challenge in competitive programming and coding interviews. It requires finding the sum of the minimum elements of all subarrays in a given array.

A naive approach using brute force has a time complexity of O(n2)O(n^2), which is inefficient for large datasets. Instead, we can optimize the solution using Stack and Queue, reducing the complexity to O(n)O(n).

In this blog, we’ll explore the optimized approach to solve the Sum of Subarray Minimum problem using monotonic stacks and discuss the role of queues in handling similar problems efficiently.

Understanding the Problem Statement

Given an array arr[] of N integers, we need to find the sum of the minimum elements for all possible subarrays.

Example:

Input:

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

All subarrays and their minimums:

• [3] → Min = 3
• [1] → Min = 1
• [2] → Min = 2
• [4] → Min = 4
• [3,1] → Min = 1
• [1,2] → Min = 1
• [2,4] → Min = 2
• [3,1,2] → Min = 1
• [1,2,4] → Min = 1
• [3,1,2,4] → Min = 1

Sum of all minimums = 3 + 1 + 2 + 4 + 1 + 1 + 2 + 1 + 1 + 1 = 17

Constraints

• 1≤N≤1051 \leq N \leq 10^5
• 1≤arr[i]≤1061 \leq arr[i] \leq 10^6

A brute-force approach won’t work efficiently for large values of NN, so we need an optimized solution.

Why Use Stack and Queue for Optimization?

To efficiently compute the sum of subarray minimums, we need a monotonic stack. This approach ensures:
✅ Efficient next smaller element and previous smaller element lookups.
✅ Reduction of time complexity to O(n)O(n) instead of O(n2)O(n^2).
✅ A stack-based traversal, avoiding unnecessary recalculations.

Queues, especially deque (double-ended queue), help in sliding window problems but are not the best fit for this exact problem.

Optimized Approach Using Monotonic Stack

The key idea is to determine the contribution of each element as the minimum in multiple subarrays using previous smaller elements (left boundary) and next smaller elements (right boundary).

Steps to Solve Using Stack:

1. Find the left boundary (Previous Less Element – PLE):
   • Using a monotonic increasing stack, determine how far left each element can be the minimum.
2. Find the right boundary (Next Less Element – NLE):
   • Again, use a monotonic increasing stack to determine how far right each element can be the minimum.
3. Calculate contribution:
   • Each element’s contribution to the total sum is determined as: arr[i]×count of subarrays where arr[i] is the minimumarr[i] \times \text{count of subarrays where } arr[i] \text{ is the minimum}

Efficient Code Implementation in Python

def sumSubarrayMins(arr):
    MOD = 10**9 + 7
    n = len(arr)
    
    # Previous Less Element (PLE)
    ple = [-1] * n
    stack = []
    
    for i in range(n):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        ple[i] = stack[-1] if stack else -1
        stack.append(i)
    
    # Next Less Element (NLE)
    nle = [n] * n
    stack = []
    
    for i in range(n-1, -1, -1):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        nle[i] = stack[-1] if stack else n
        stack.append(i)
    
    # Calculate sum of minimums
    total_sum = 0
    for i in range(n):
        left = i - ple[i]
        right = nle[i] - i
        total_sum += (arr[i] * left * right) % MOD
    
    return total_sum % MOD

# Example usage
arr = [3, 1, 2, 4]
print(sumSubarrayMins(arr))  # Output: 17

Time Complexity Analysis

Approach	Time Complexity
Brute Force	O(n2)O(n^2)
Stack Optimization	O(n)O(n)

Since each element is pushed and popped from the stack at most once, the overall complexity is O(n)O(n), making it highly efficient.

---

Edge Cases Considered

✔ Single element array → [5] should return 5
✔ All elements same → [2,2,2] should handle duplicates correctly
✔ Decreasing order → [4,3,2,1] tests monotonic behavior
✔ Increasing order → [1,2,3,4] ensures correct right-boundary calculation

Common Mistakes to Avoid

❌ Using > instead of >= in the Next Less Element stack check.
❌ Forgetting to consider modulo constraints for large outputs.
❌ Miscalculating left and right subarray contributions.

FAQs

Conclusion

The Sum of Subarray Minimum problem can be efficiently solved using monotonic stacks. By finding the Previous Less Element (PLE) and Next Less Element (NLE), we reduce the complexity from O(n2)O(n^2) to O(n)O(n).

Understanding Stack and Queue concepts is crucial for solving range-based queries effectively in coding interviews and real-world applications.

Try implementing this approach in your next coding challenge!