Subarrays with First Element Minimum

JavaView on GFG

Time: O(n)

Space: O(n)

Problem Overview

Count subarrays where the first element is the minimum.

See our study guide for structured GFG and LeetCode practice.

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?