abhinav5481

Sum of Subarray Minimums

Oct 17th, 2021
673
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.     public int sumSubarrayMins(int[] arr) {
  3.         int len = arr.length;
  4.         int[] left = new int[len];
  5.         int[] right = new int[len];
  6.        
  7.         Stack<int[]> stack = new Stack<>();
  8.         for(int i = 0 ; i < len ; i++){
  9.            int count = 1;
  10.                 while( stack.size() > 0 &&  stack.peek()[0] >= arr[i]){
  11.                     int[] popped = stack.pop();
  12.                     count += popped[1];
  13.                 }
  14.                
  15.                
  16.             stack.push(new int[]{arr[i],count,i});
  17.             left[i] = count;
  18.            
  19.         }
  20.        
  21.         stack.clear();
  22.        
  23.         for(int i = len-1; i >= 0 ; i--){
  24.            
  25.                 int count = 1;
  26.                 while( stack.size() > 0 &&  stack.peek()[0] > arr[i]){
  27.                     int[] popped = stack.pop();
  28.                     count += popped[1];
  29.                 }
  30.                
  31.                
  32.                 stack.push(new int[]{arr[i],count,i});
  33.             right[i] = count;
  34.            
  35.         }
  36.        
  37.         long sum = 0;
  38.         int mod = 1000000007;
  39.          for(int i = 0 ; i < len ; i++){
  40.              long  temp = ((left[i] % mod )* 1L * (right[i] % mod)) % mod;
  41.              temp = ((arr[i] % mod ) *1L* (temp % mod)) % mod;
  42.              sum = (sum % mod+ temp % mod) % mod;
  43.          }
  44.         return (int)sum;
  45.        
  46.        
  47.     }
  48. }
RAW Paste Data