Subarrays with First Element Minimum

class Solution {
public:
    long long countSubarrays(vector<int>& arr) {
        int n = arr.size();
        stack<int> st;
        long long ans = 0;

        for(int i = n - 1; i >= 0; i--) {
            while(!st.empty() && arr[st.top()] >= arr[i])
                st.pop();

            int nextSmaller = st.empty() ? n : st.top();
            ans += (nextSmaller - i);

            st.push(i);
        }

        return ans;
    }
};

class Solution {
    public long countSubarrays(int[] arr) {
        int n = arr.length;
        Stack<Integer> st = new Stack<>();
        long ans = 0;

        for(int i = n - 1; i >= 0; i--) {
            while(!st.isEmpty() && arr[st.peek()] >= arr[i])
                st.pop();

            int nextSmaller = st.isEmpty() ? n : st.peek();
            ans += nextSmaller - i;

            st.push(i);
        }

        return ans;
    }
}

class Solution {
    countSubarrays(arr) {
        let n = arr.length;
        let stack = [];
        let ans = 0;

        for (let i = n - 1; i >= 0; i--) {
            while (stack.length && arr[stack[stack.length - 1]] >= arr[i]) {
                stack.pop();
            }

            let nextSmaller = stack.length ? stack[stack.length - 1] : n;
            ans += nextSmaller - i;

            stack.push(i);
        }

        return ans;
    }
}

class Solution:
    def countSubarrays(self, arr):
        n = len(arr)
        stack = []
        ans = 0

        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()

            next_smaller = stack[-1] if stack else n
            ans += next_smaller - i

            stack.append(i)

        return ans

[i ... j]

nextSmaller[i] = index of next element smaller than arr[i]

[i]
[i, i+1]
[i, i+2]
...
[i, nextSmaller[i]-1]

count = nextSmaller[i] - i
// If there is no smaller element, then: count = n - i

class Solution {
  public:
    long long countSubarrays(vector<int>& arr) {
        int n = arr.size();
        stack<int> st;
        long long res = 0;

        for(int i = 0; i < n; i++) {
            while(!st.empty() && arr[i] < arr[st.top()]) {
                int idx = st.top();
                st.pop();
                res += (i - idx);
            }
            st.push(i);
        }

        while(!st.empty()) {
            int idx = st.top();
            st.pop();
            res += (n - idx);
        }

        return res;
    }
};

import java.util.*;

class Solution {
    public long countSubarrays(int[] arr) {
        int n = arr.length;
        Stack<Integer> st = new Stack<>();
        long res = 0;

        for(int i = 0; i < n; i++) {
            while(!st.isEmpty() && arr[i] < arr[st.peek()]) {
                int idx = st.pop();
                res += (i - idx);
            }
            st.push(i);
        }

        while(!st.isEmpty()) {
            int idx = st.pop();
            res += (n - idx);
        }

        return res;
    }
}

class Solution {
    countSubarrays(arr) {
        let n = arr.length;
        let stack = [];
        let res = 0;

        for (let i = 0; i < n; i++) {
            while (stack.length && arr[i] < arr[stack[stack.length - 1]]) {
                let idx = stack.pop();
                res += (i - idx);
            }
            stack.push(i);
        }

        while (stack.length) {
            let idx = stack.pop();
            res += (n - idx);
        }

        return res;
    }
}

class Solution:
    def countSubarrays(self, arr):
        n = len(arr)
        stack = []
        res = 0

        for i in range(n):
            while stack and arr[i] < arr[stack[-1]]:
                idx = stack.pop()
                res += (i - idx)

            stack.append(i)

        while stack:
            idx = stack.pop()
            res += (n - idx)

        return res