10. Subarrays with First Element Minimum

✅ GFG solution to the Subarrays with First Element Minimum problem: count subarrays where the first element is the minimum using monotonic stack technique. 🚀

The problem can be found at the following link: 🔗 Question Link

🧩 Problem Description

You are given an integer array arr[]. Your task is to count the number of subarrays where the first element is the minimum element of that subarray.

A subarray is valid if its first element is not greater than any other element in that subarray.

📘 Examples

Example 1

Input: arr[] = [1, 2, 1]
Output: 5
Explanation:
All possible subarrays are:
[1], [1, 2], [1, 2, 1], [2], [2, 1], [1]
Valid subarrays are:
[1], [1, 2], [1, 2, 1], [2], [1] → total 5

Example 2

Input: arr[] = [1, 3, 5, 2]
Output: 8
Explanation:
Valid subarrays are: [1], [1, 3], [1, 3, 5], [1, 3, 5, 2], [3], [3, 5], [5], [2] → total 8

🔒 Constraints

$1 \le \text{arr.size()} \le 5 \times 10^4$
$1 \le \text{arr}[i] \le 10^5$

✅ My Approach

The optimal approach uses a Monotonic Stack traversed from right to left to efficiently determine for each index how far the subarray can extend while keeping the first element as the minimum:

Monotonic Stack (Right to Left)

Key Observation:
- For any index i, arr[i] remains the minimum of subarray arr[i..j] as long as no element in arr[i+1..j] is strictly less than arr[i].
- So we need to find the next index to the right where a strictly smaller element appears — call it nxt.
- The number of valid subarrays starting at i is exactly nxt - i.
Traverse Right to Left:
- Maintain an array-based monotonic stack that stores indices in increasing order of their values (from bottom to top).
- For each index i (moving right to left), pop all stack entries whose corresponding values are ≥ arr[i] — those are no longer useful as "next smaller" boundaries.
- The top of the stack now holds the index of the next element strictly smaller than arr[i].
Count Contribution:
- If the stack is empty, all indices from i to n-1 are valid, so add n - i.
- Otherwise, add st[top] - i, where st[top] is the nearest smaller boundary.
Push Current Index:
- Push i onto the stack for future elements to use as their boundary.
Accumulate and Return:
- Sum all contributions and return the total count.

📝 Time and Auxiliary Space Complexity

Expected Time Complexity: O(n), as each element is pushed onto and popped from the stack at most once, resulting in a total of at most 2n stack operations across the entire traversal.
Expected Auxiliary Space Complexity: O(n), as the stack can hold at most n indices in the worst case (e.g., a strictly decreasing array where no element is ever popped).

🧑‍💻 Code (C++)

class Solution {
public:
    int countSubarrays(vector<int>& arr) {
        int n = arr.size(), top = -1, ans = 0;
        vector<int> st(n);
        for (int i = n - 1; i >= 0; i--) {
            while (top >= 0 && arr[st[top]] >= arr[i]) top--;
            ans += ((top < 0 ? n : st[top]) - i);
            st[++top] = i;
        }
        return ans;
    }
};

⚡ View Alternative Approaches with Code and Analysis

📊 2️⃣ Standard Stack Approach

💡 Algorithm Steps:

Traverse array from right to left using a standard STL monotonic stack.
For each index, pop elements from the stack while they are greater than or equal to the current element.
The stack top gives the next strictly smaller element's index — this becomes the right boundary.
Add (boundary - i) to the answer and push the current index.

class Solution {
public:
    int countSubarrays(vector<int>& arr) {
        stack<int> st;
        int ans = 0, n = arr.size();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && arr[st.top()] >= arr[i]) st.pop();
            int nxt = st.empty() ? n : st.top();
            ans += nxt - i;
            st.push(i);
        }
        return ans;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n) — Each element is pushed and popped at most once
Auxiliary Space: 💾 O(n) — Stack can hold up to n elements

✅ Why This Approach?

Most readable and standard implementation using STL.
Clear monotonic stack pattern with intuitive variable naming.
Easy to debug and verify correctness.

📊 3️⃣ Next Smaller Precomputation

💡 Algorithm Steps:

Precompute the next strictly smaller element's index for each position using a monotonic stack in a separate pass.
Store boundaries in a nxt[] array; default value is n (meaning no smaller element exists).
In a second pass, sum up nxt[i] - i for all indices to get the final count.

class Solution {
public:
    int countSubarrays(vector<int>& arr) {
        int n = arr.size();
        vector<int> nxt(n, n);
        stack<int> st;
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && arr[st.top()] >= arr[i]) st.pop();
            if (!st.empty()) nxt[i] = st.top();
            st.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) ans += nxt[i] - i;
        return ans;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n) — Two independent linear passes through the array
Auxiliary Space: 💾 O(n) — Extra nxt[] array plus the stack

✅ Why This Approach?

Cleanly separates the precomputation and accumulation phases.
The nxt[] array is reusable if boundary information is needed later.
Easier to test boundary values individually.

📊 4️⃣ Greedy Expansion Approach

💡 Algorithm Steps:

For each starting index i, greedily extend the subarray to the right.
Continue extending as long as the next element is greater than or equal to arr[i] (keeping arr[i] the minimum).
Count all valid subarrays that start at i as (j - i + 1) where j is the furthest valid index.
No extra data structure is needed — direct comparison.

class Solution {
public:
    int countSubarrays(vector<int>& arr) {
        int n = arr.size(), ans = 0;
        for (int i = 0; i < n; i++) {
            int j = i;
            while (j + 1 < n && arr[i] <= arr[j + 1]) j++;
            ans += j - i + 1;
        }
        return ans;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n²) worst case, O(n) for strictly decreasing sequences
Auxiliary Space: 💾 O(1) — No extra space required

✅ Why This Approach?

Simple and intuitive — no stack or extra data structure needed.
Great for understanding the problem from first principles.
Works efficiently in practice for random or nearly decreasing inputs.

⚠️ Note: This approach results in Time Limit Exceeded (TLE) for large inputs near the constraint boundary. (fails ~1010/1120 test cases due to time constraints).

🆚 🔍 Comparison of Approaches

🚀 Approach

⏱️ Time Complexity

💾 Space Complexity

✅ Pros

⚠️ Cons

🏷️ Array-Based Stack

🟢 O(n)

🚀 Fastest, cache-friendly

🔧 Manual stack management

🔍 Standard Stack

🟢 O(n)

📖 Most readable

💾 STL overhead

📊 Precomputation

🟢 O(n)

🟡 O(n)

🎯 Clear separation of phases

💾 Extra array storage

🔄 Greedy Expansion

🟡 O(n²) worst

🟢 O(1)

⭐ No extra space, simple logic

🔧 Worst case quadratic, TLE risk

🏆 Best Choice Recommendation

🎯 Scenario

🎖️ Recommended Approach

🔥 Performance Rating

🏅 Competitive Programming

🥇 Array-Based Stack

★★★★★

📖 Readability & Debugging

🥈 Standard Stack

★★★★☆

🔧 Need Boundary Information

🥉 Precomputation

★★★★☆

🎯 Space Critical / Small Inputs

🏅 Greedy Expansion

★★★☆☆

☕ Code (Java)

class Solution {
    public int countSubarrays(int[] arr) {
        int n = arr.length, top = -1, ans = 0;
        int[] st = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            while (top >= 0 && arr[st[top]] >= arr[i]) top--;
            ans += ((top < 0 ? n : st[top]) - i);
            st[++top] = i;
        }
        return ans;
    }
}

🐍 Code (Python)

class Solution:
    def countSubarrays(self, arr):
        st, ans, n = [], 0, len(arr)
        for i in range(n - 1, -1, -1):
            while st and arr[st[-1]] >= arr[i]: st.pop()
            ans += ((st[-1] if st else n) - i)
            st.append(i)
        return ans

🧠 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

📍Visitor Count

Previous09. Largest Number in One Swap Next11. Sum of Subarray Minimums

Last updated 8 days ago

hashtag🧩 Problem Description

hashtag📘 Examples

hashtagExample 1

hashtagExample 2

hashtag🔒 Constraints

hashtag✅ My Approach

hashtagMonotonic Stack (Right to Left)

hashtag📝 Time and Auxiliary Space Complexity

hashtag🧑‍💻 Code (C++)

hashtag📊 2️⃣ Standard Stack Approach

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 3️⃣ Next Smaller Precomputation

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 4️⃣ Greedy Expansion Approach

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag🆚 🔍 Comparison of Approaches

hashtag🏆 Best Choice Recommendation

hashtag☕ Code (Java)

hashtag🐍 Code (Python)

hashtag🧠 Contribution and Support

hashtag📍Visitor Count

🧩 Problem Description

📘 Examples

Example 1

Example 2

🔒 Constraints

✅ My Approach

Monotonic Stack (Right to Left)

📝 Time and Auxiliary Space Complexity

🧑‍💻 Code (C++)

📊 2️⃣ Standard Stack Approach

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 3️⃣ Next Smaller Precomputation

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 4️⃣ Greedy Expansion Approach

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

🆚 🔍 Comparison of Approaches

🏆 Best Choice Recommendation

☕ Code (Java)

🐍 Code (Python)

🧠 Contribution and Support

📍Visitor Count