Subarrays with First Element Minimum

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Count subarrays where the first element is the minimum. Monotonic stack.

Algorithm

1For each index i: find how far right arr[i] remains the minimum (next smaller element). Count = span length.

Common Pitfalls

•Use monotonic stack to find next smaller element. For each position, count valid subarrays starting here.

Subarrays with First Element Minimum.java

Java

// Approach: For each element, find previous smaller and next smaller-or-equal. Count subarrays where it's first min.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public int countSubarrays(int[] arr) {
        int n = arr.length, cnt = 0;
        LinkedList<Integer> lt = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            cnt += (n - i);
            while (!lt.isEmpty() && arr[lt.getLast()] > arr[i]) {
                cnt += (i - n);
                lt.removeLast();
            }
            lt.add(i);
        }
        
        return cnt;
    }
}

Was this solution helpful?