Sum of Subarray Minimums

Introduction

• Problem: Given an array of numbers, calculate the sum of the minimum values of all possible subarrays.
• The result may be large, so we will take the modulo with ( 10^9 + 7 ).

Understanding Subarrays

• A subarray is a contiguous portion of an array.

• For example, given the array [3, 1, 2, 4], the possible subarrays are:

  • Starting with 3:
    • [3], [3, 1], [3, 1, 2], [3, 1, 2, 4]
  • Starting with 1:
    • [1], [1, 2], [1, 2, 4]
  • Starting with 2:
    • [2], [2, 4]
  • Starting with 4:
    • [4]

• Each subarray has a minimum value:

  • Minimum of [3] = 3, [3, 1] = 1, [3, 1, 2] = 1, [3, 1, 2, 4] = 1, etc.

• Sum of minima: 3 + 1 + 1 + 1 + 1 + 2 + 2 + 4 = 17.

Brute Force Solution

• The simplest method is to generate all possible subarrays and calculate the sum of their minimums.
• Time Complexity: O(n^2) due to nested loops generating subarrays.
• Space Complexity: O(1) as we are using constant space.

Optimized Approach

Contribution of Each Element

• Instead of generating all subarrays, calculate how many times each element is the minimum in subarrays.
• How do we know how many times an element contributes?
  • Count how many elements on the left are greater than or equal to the current element (previous smaller element).
  • Count how many elements on the right are smaller than the current element (next smaller element).
• Formula for the contribution:
  • Contribution of element at index ( i ) = Count on left × Count on right × Element value.

Prerequisites

• Understanding of Next Greater Element (NGE) and Previous Smaller Element (PSE).
• Be familiar with finding the Next Smaller Element (NSE) and Previous Smaller Element (PSE).

Finding Next and Previous Smaller Elements

1. Next Smaller Element (NSE)
   • Traverse the array from right to left.
   • Store indices in a stack; if the current element is smaller than the top of the stack, pop until you find a smaller element or the stack is empty.
   • If the stack is empty, that means there’s no smaller element on the right, so store n (length of the array).
2. Previous Smaller Element (PSE)
   • Traverse the array from left to right.
   • Similar logic as NSE, but looking for smaller elements on the left.
   • If no smaller element, store -1.

Contribution Calculation

• Count left: Current index – Previous Smaller Element Index.
• Count right: Next Smaller Element Index – Current Index.
• Combine these counts to get total contributions.
• Update total count using contributions of each element.

Implementation Plan

1. Initialize the sum and setup for modulus calculation (( 10^9 + 7 )).
2. Implement functions to find NSE and PSE.
3. Loop through the array and calculate contributions using NSE and PSE.
4. Return the sum after all contributions are added.

Edge Cases

• Consider arrays with duplicate elements carefully to avoid double counting.
• Adjust the logic for Previous Smaller Element to account for equal values (use Previous Smaller or Equal Element).

Complexity Analysis

• Time Complexity: O(n) for calculating NSE and PSE with a stack.
• Overall Complexity: Approximately O(n) due to efficient calculations.
• Space Complexity: O(n) for stacks used to store indices.

Conclusion

• Understanding the contributions of each element optimizes the computation significantly.
• Ensure to follow prerequisites before deeper implementations and optimize wherever possible.