907. Sum of Subarray Minimums

Hello, reader 👋🏽 ! Welcome to day 55 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 907. Sum of Subarray Minimums.

🤔 Problem Statement

Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighbouring. The same letter cell may not be used more than once.
E.g.:
- arr = [3,1,2,4] => 17
- arr = [11,81,94,43,3] => 444

💬 Thought Process - Monotonic Stack

This solution is built from the naive solution where we generate all the subarrays and add the minimum number of each subarray to the total sum.
The idea behind this approach is to focus on the minimum numbers across the the entire array.
If we somehow find the number of subarrays in which any element is minimum, we can easily find the contribution of this element in the total sum by: x * number of subarrays where x is minimum.
Extending this to the entire array, we can easily get the total sum.
Let's understand this with the help of the given test case: arr = [11,81,94,43,3] . Initially, sum = 0
- subarrays where 11 is the minimum: [11], [11,81], [11,81,94], [11,81,94,43] => sum = sum + (11 * 4).
- subarrays where 81 is the minimum: [81], [81,94] => sum = sum + (2 * 81).
- subarrays where 94 is the minimum: [94] => sum = sum + (1 * 94).
- subarrays where 43 is the minimum: [81,94,43], [94,43], [43] => sum = sum + (3 * 43).
- subarrays where 3 is the minimum: [11,81,94,43,3], [81,94,43,3], [94,43,4], [43,3], [3] => sum = sum + (5 * 3).
- Total Sum is: => 444
But to calculate the count of subarrays with minimum number x, we'd actually require the range of the subarray containing this x.
This can be boiled down to finding number prev at index i such that prev <= x and another number next at index k such that x >= next, where i < j < k. Let's assume x is at index j.
Hence, the range of subarray where x is the smallest would be: [i+1, k-1].
Basically we want to find the previous smallest element and the next smallest element for all numbers x in the array. To do so, we can build a monotonic stack which is strictly increasing with the <index, value> pair.
For the first element, there's no previous smaller element. Hence, we directly push <0, val>.
If the stack is not empty, then we keep popping of the top of the stack until the top element is smaller than the current element.
That means, we pop all the elements that are greater than the current element.
For every element popped,
For every pair we pop, we count the range in which the popped element was the smallest.
To find the range, we split it into two halves:
1. left side of the popped element
2. right side of the popped element.
We know the current popped element is larger than the element in the top of the stack. So we can easily calculate the number of elements in the left range by popped element index - current top element index. If the stack is empty, then we can assume the previous smaller as -1.
We can see that the element being processed is going to be smaller than the popped element. Hence to get the right side range: current index - popped element index.
For every element in both these ranges, the popped element would be the smallest. Hence we multiply the number of elements in both ranges with the popped element's value. This total is added to the sum.
This can be quite confusing, so let's understand this with the help of an example.

There are two observations here:
1. For any duplicates in the list we should only include one of them across a single subarray. E.g. [3, 1, 5, 2, 6, 2, 8, 2, 1], here 2 at index 5 would have 3 elements in the range towards the left and 1 element in the range towards right. Hence, [5, 2, 6, 2, 8] would what our current algorithm find for 2 at index 5.
2. We'll run our loop from 0 to n so that we process the smaller elements that remain behind once the iteration ends. In this example, we'll have the pair <8, 1> at index after the iteration of the array. We can include this 1 as a part of the minimum in all the elements towards its left. Hence it would be the minimum as a part of 9 subarrays.

👩🏽‍💻 Solution - Monotonic Stack

Below is the code for the monotonic stack approach.

class Solution {
  private int mod = (int) 1e9 + 7; 
  public int sumSubarrayMins(int[] arr) {
      int n = arr.length;

      int sum = 0;
      Stack<Pair<Integer, Integer>> stack = new Stack();

      for(int rightIndex = 0; rightIndex<=n; rightIndex++) {
          while(!stack.isEmpty() && 
                (rightIndex == n || 
                 stack.peek().getValue() >= arr[rightIndex])
          ) {
              Pair<Integer, Integer> mid = stack.pop();
              int midIndex = mid.getKey();
              int midVal = mid.getValue();

              int leftIndex = -1;
              if(!stack.isEmpty()) {
                  Pair<Integer, Integer> left = stack.peek();
                  leftIndex = left.getKey();
              }
              long numArrays = ((rightIndex - midIndex) * (midIndex - leftIndex)) % mod;
              long numSum = numSubsets * midVal;

              sum = (int) ((sum + numSum) % mod);

          }
          int num = (rightIndex == n) ? -1 : arr[rightIndex];
          stack.push(new Pair(rightIndex, num));
      }

      return sum;
  }
}

Time Complexity: O(n)
- m = length of the array
Space Complexity: O(n)
- n = length of the array
    - We use a stack to keep track of all the smallest elements

There's another approach using Dynamic Programming and Monotonic Stack that's explained in LeetCode which you can check out.
You can find the link to the GitHub repo for this question here: 907. Sum of Subarray Minimums.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

Bharati Subramanian