The O(n) Club: Subarray Minimums & The Stack That Outsmarts Brute Force

The O(n) Club: Subarray Minimums & The Stack That Outsmarts Brute Force

⚡ TL;DR

Want to sum up the minimum of every contiguous subarray? Brute force is a torture device. Use monotonic stacks instead! For the curious, here’s what NOT to do (unless your hobby is infinite runtime):

// Yikes, the slow highway.
int sumSubarrayMins(int[] A) {
    int n = A.length, mod = (int)1e9+7, res = 0;
    for (int i = 0; i < n; ++i)
      for (int j = i; j < n; ++j) {
        int min = A[i];
        for (int k = i; k <= j; ++k) min = Math.min(min, A[k]);
        res = (res + min) % mod;
      }
    return res;
}
// Use if you want to retire before your function returns.

🧠 How Devs Usually Mess This Up

We’ve all written the “let’s just try every subarray, how bad could it be?” triple-nested loop. Spoiler: It’s bad. Even with two loops, your algorithm will groan, sigh, and eventually betray you with Time Limit Exceeded (TLE). Most devs build all subarrays, find their mins, and pray nobody asks for an array longer than 10. Managers and interviewers will see this coming like a car crash in slow motion. You can do better—trust me, and trust the stack.

🔍 What’s Actually Going On

Stop checking every room for the quietest person—instead, make each person count how many rooms they shout the lowest. For each element A[i], find: in how many subarrays is A[i] the minimum? Count those, multiply by the value, and add up everyone. How many subarrays claim A[i] as their minimum? Look left and right: how far until someone smaller (on the left) or smaller or equal (on the right) appears. Monotonic stacks let you count this in O(n) time without going bug-eyed.

🛠️ PseudoCode

• For each index:
  • Calculate left[i]: How many consecutive elements to the left (including i) before hitting a strictly smaller element.
  • Calculate right[i]: How many consecutive elements to the right (including i) before hitting a smaller or equal element.

  // All the caffeine, none of the O(n^3)
  Stack<Integer> stack = new Stack<>();
  int[] left = new int[n], right = new int[n];
   // Compute left counts
  for (int i = 0; i < n; ++i) {
      while (!stack.isEmpty() && A[stack.peek()] > A[i]) stack.pop();
      left[i] = stack.isEmpty() ? (i+1) : (i - stack.peek());
      stack.push(i);
  }
   // Compute right counts
  stack.clear();
  for (int i = n-1; i >= 0; --i) {
      while (!stack.isEmpty() && A[stack.peek()] >= A[i]) stack.pop();
      right[i] = stack.isEmpty() ? (n-i) : (stack.peek() - i);
      stack.push(i);
  }
   // Multiply and sum contributions
  for (int i = 0; i < n; ++i)
      res = (res + A[i] * left[i] * right[i]) % mod;
  

• Each element’s total impact is its value * left * right.

💻 The Code

// Fast enough for humans, machines, and interviewers
public int sumSubarrayMins(int[] A) {
    int n = A.length, mod = (int)1e9 + 7;
    int[] left = new int[n], right = new int[n];
    Stack
<integer> stack = new Stack<>();
     // Calculate left distances
    for (int i = 0; i < n; ++i) {
        while (!stack.isEmpty() && A[stack.peek()] > A[i]) stack.pop();
        left[i] = stack.isEmpty() ? (i+1) : (i - stack.peek());
        stack.push(i);
    }
    
    // Calculate right distances
    stack.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!stack.isEmpty() && A[stack.peek()] >= A[i]) stack.pop();
        right[i] = stack.isEmpty() ? (n-i) : (stack.peek() - i);
        stack.push(i);
    }
     long res = 0;
    for (int i = 0; i < n; ++i)
        res = (res + (long)A[i] * left[i] * right[i]) % mod;
    return (int)res;
}
</integer>

⚠️ Pitfalls, Traps & Runtime Smacks

• Boundary Fumbles: Off-by-one in left/right = 50% of bug reports. Test tiny arrays before trusting big ones.
• Duplicate Drama: For right bounds, treat equals as “end of influence.” (>= in that while!)
• Overflow Meltdowns: Multiply with long or you’ll see negative subarray karma.
• Space-Time Trade: O(n) stacks + arrays. Perfectly reasonable—unless your server runs on hamster wheels.

🧠 Interviewer Brain-Tattoo

“Every brute force has spirit, but only stacks deliver salvation. Count, multiply, coffee break.”