# Find the Number of Subarrays Where Boundary Elements Are Maximum
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-number-of-subarrays-where-boundary-elements-are-maximum)
Canonical: https://scaleengineer.com/dsa/problems/find-the-number-of-subarrays-where-boundary-elements-are-maximum
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Stack, Monotonic Stack
---
## Problem
You are given an array of **positive** integers `nums`.

Return the number of subarrays of `nums`, where the **first** and the **last** elements of the subarray are _equal_ to the **largest** element in the subarray.

**Example 1:**

**Input:** nums = \[1,4,3,3,2\]

**Output:** 6

**Explanation:**

There are 6 subarrays which have the first and the last elements equal to the largest element of the subarray:

* subarray `[**1**,4,3,3,2]`, with its largest element 1\. The first element is 1 and the last element is also 1.
* subarray `[1,**4**,3,3,2]`, with its largest element 4\. The first element is 4 and the last element is also 4.
* subarray `[1,4,**3**,3,2]`, with its largest element 3\. The first element is 3 and the last element is also 3.
* subarray `[1,4,3,**3**,2]`, with its largest element 3\. The first element is 3 and the last element is also 3.
* subarray `[1,4,3,3,**2**]`, with its largest element 2\. The first element is 2 and the last element is also 2.
* subarray `[1,4,**3,3**,2]`, with its largest element 3\. The first element is 3 and the last element is also 3.

Hence, we return 6.

**Example 2:**

**Input:** nums = \[3,3,3\]

**Output:** 6

**Explanation:**

There are 6 subarrays which have the first and the last elements equal to the largest element of the subarray:

* subarray `[**3**,3,3]`, with its largest element 3\. The first element is 3 and the last element is also 3.
* subarray `[3,**3**,3]`, with its largest element 3\. The first element is 3 and the last element is also 3.
* subarray `[3,3,**3**]`, with its largest element 3\. The first element is 3 and the last element is also 3.
* subarray `[**3,3**,3]`, with its largest element 3\. The first element is 3 and the last element is also 3.
* subarray `[3,**3,3**]`, with its largest element 3\. The first element is 3 and the last element is also 3.
* subarray `[**3,3,3**]`, with its largest element 3\. The first element is 3 and the last element is also 3.

Hence, we return 6.

**Example 3:**

**Input:** nums = \[1\]

**Output:** 1

**Explanation:**

There is a single subarray of `nums` which is `[**1**]`, with its largest element 1\. The first element is 1 and the last element is also 1.

Hence, we return 1.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Brute Force
The brute-force approach involves generating every possible subarray and checking if it meets the specified criteria. A subarray is defined by its start and end indices. We can use nested loops to iterate through all possible start (`i`) and end (`j`) indices. For each subarray, we then verify if the first and last elements are equal to the maximum element within that subarray.
**Time:** O(n^2), where n is the number of elements in the array. The nested loops iterate through approximately n^2 / 2 subarrays. · **Space:** O(1) extra space, as we only use a few variables to store the count and loop indices.
**Pros:** Simple to understand and implement.; Uses constant extra space.
**Cons:** The time complexity of O(n^2) can be too slow for large inputs, potentially leading to a 'Time Limit Exceeded' error on platforms with strict time limits.
### Explanation
We can iterate through all possible subarrays using two nested loops. The outer loop selects the starting element `nums[i]`, and the inner loop selects the ending element `nums[j]`. For each subarray `nums[i..j]`, we must verify the condition: `nums[i] == nums[j] == max(nums[k])` for `i <= k <= j`.

A naive check would involve a third loop to find the maximum in `nums[i..j]`, leading to an O(n^3) solution. However, we can optimize this to O(n^2) by observing that as we extend the subarray from `nums[i..j]` to `nums[i..j+1]`, the maximum can be updated in O(1) time. We maintain a running maximum for the subarray starting at `i` as we iterate `j`.

For each starting index `i`, we initialize `current_max` with `nums[i]`. Then, as we iterate with `j` from `i` to the end of the array, we update `current_max` and check if `nums[i] == nums[j]` and `nums[i] == current_max`. If so, we've found a valid subarray.

```java
class Solution {
    public long numberOfSubarrays(int[] nums) {
        int n = nums.length;
        long count = 0;

        for (int i = 0; i < n; i++) {
            int currentMax = nums[i];
            for (int j = i; j < n; j++) {
                // As we expand the subarray to the right, if we find an element
                // greater than the starting element, no further subarray starting at i
                // can be valid.
                if (nums[j] > nums[i]) {
                    break;
                }
                // If nums[j] equals nums[i], it's a valid subarray because all elements
                // seen so far between i and j are less than or equal to nums[i].
                if (nums[j] == nums[i]) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Iterate through the array with an outer loop using index `i` from `0` to `n-1`, where `n` is the length of the array. This `i` will be the starting index of a subarray.
3. Inside the outer loop, start an inner loop with index `j` from `i` to `n-1`. This `j` will be the ending index of a subarray.
4. For each subarray `nums[i..j]`, we need to check if it satisfies the condition.
5. To do this efficiently within the loops, maintain a variable `current_max` that tracks the maximum value in the subarray `nums[i..j]` as `j` increases.
6. In the inner loop, update `current_max = max(current_max, nums[j])`.
7. Check if the boundary elements are equal to this maximum: `nums[i] == nums[j]` and `nums[i] == current_max`.
8. If the condition is met, increment the `count`.
9. After the loops complete, return the total `count`.

## Next Greater Element with Binary Search
A more optimized approach improves upon the brute-force by avoiding redundant checks. The condition `max(nums[i..j]) == nums[i]` implies that no element between `i` and `j` can be greater than `nums[i]`. This means `j` must be smaller than the index of the *Next Greater Element* (NGE) for `nums[i]`.

We can precompute the NGE for every element in O(n). Then, for each element `nums[i]`, we need to count how many times `nums[i]` appears in the range from `i` up to (but not including) its NGE's index. This counting can be done efficiently if we pre-group all indices by their values and then use binary search.
**Time:** O(n log n). O(n) for NGE and map creation. The main loop runs `n` times, and each iteration involves a binary search on a list of indices. The sum of lengths of all lists is `n`, leading to a total time of O(n log n) in the worst case. · **Space:** O(n) for storing the `nge` array, the stack for NGE computation, and the hash map which can store up to `n` indices in total.
**Pros:** Significantly faster than the brute-force approach for large inputs.; The logic is systematic and breaks the problem down into standard subproblems (NGE, binary search).
**Cons:** Requires extra space for the NGE array and the hash map.; The `log n` factor in the time complexity might be slightly slower than a linear-time solution for very large `n`.
### Explanation
The core idea is to rephrase the condition. For a subarray `nums[i..j]` to be valid, we need `nums[i] == nums[j]` and `nums[k] <= nums[i]` for all `k` from `i` to `j`. The second part is equivalent to saying that the index `j` must be less than the index of the next element to the right of `i` that is strictly greater than `nums[i]`. Let's call this `nge[i]`.

First, we can precompute the `nge` array for all indices in O(n) time using a monotonic stack. We iterate from right to left, maintaining a stack of indices of elements in increasing order.

Second, we create a `HashMap<Integer, List<Integer>>` to store the indices of each unique number. This allows us to quickly access all positions of a certain value.

Finally, we iterate through each index `i` of the `nums` array. For each `nums[i]`, we know its valid partners `nums[j]` must occur before `nge[i]`. We look up `nums[i]` in our hash map to get a sorted list of its occurrences. We then use binary search on this list to count how many of these occurrences fall in the range `[i, nge[i])`. Summing these counts for all `i` gives the total number of valid subarrays.

```java
import java.util.*;

class Solution {
    public long numberOfSubarrays(int[] nums) {
        int n = nums.length;
        
        // Step 1: Precompute Next Greater Element
        int[] nge = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
                stack.pop();
            }
            nge[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }
        
        // Step 2: Group indices by value
        Map<Integer, List<Integer>> valToIndices = new HashMap<>();
        for (int i = 0; i < n; i++) {
            valToIndices.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }
        
        // Step 3: Iterate and count using binary search
        long count = 0;
        for (int i = 0; i < n; i++) {
            int limit = nge[i];
            List<Integer> indices = valToIndices.get(nums[i]);
            
            // Binary search for the start index 'i'
            int startPos = Collections.binarySearch(indices, i);
            
            // Binary search for the limit
            int endPos = Collections.binarySearch(indices, limit);
            if (endPos < 0) {
                endPos = -endPos - 1;
            }
            
            count += (endPos - startPos);
        }
        
        return count;
    }
}
```
### Algorithm
1. **Precompute Next Greater Element (NGE):** Create an array `nge` of the same size as `nums`. `nge[i]` will store the index of the first element to the right of `i` that is greater than `nums[i]`. This can be computed in O(n) time using a monotonic stack. If no such element exists, we can store `n`.
2. **Group Indices by Value:** Create a hash map where keys are the numbers in `nums` and values are lists of indices where these numbers appear. This takes O(n) time.
3. **Iterate and Count:** Initialize a counter `count` to 0. Iterate through the array from `i = 0` to `n-1`.
4. For each index `i`, let `x = nums[i]`. The valid subarrays starting at `i` must end at an index `j` such that `i <= j < nge[i]` and `nums[j] == x`.
5. Use the map from step 2 to get the list of all indices where `x` appears. This list is sorted.
6. On this list of indices, perform a binary search (e.g., using `lower_bound` or equivalent) to find the number of indices that fall within the range `[i, nge[i])`.
7. Add this number to the total `count`.
8. Return the final `count`.

## Optimal Monotonic Stack Approach
The most efficient solution uses a monotonic stack to solve the problem in linear time. The key insight is to count the valid subarrays on the fly as we iterate through the array. A monotonic stack, which keeps elements in a specific order (e.g., decreasing), is a powerful tool for problems involving ranges and comparisons like 'next greater/smaller element'.

We process the array from left to right. The stack will store pairs `(value, frequency)`, representing a sequence of identical values that are only preceded by larger values. When we encounter a new number, we adjust the stack and update our count based on the relationships between the new number and the elements on the stack.
**Time:** O(n), as each element from the input array is pushed onto and popped from the stack at most once. · **Space:** O(n) in the worst case. For an input array that is strictly decreasing, the stack will store `n` elements.
**Pros:** Optimal time complexity of O(n).; Solves the problem in a single pass through the array.
**Cons:** The logic can be less intuitive to grasp compared to the brute-force approach.; Requires O(n) extra space for the stack in the worst-case scenario (e.g., a strictly decreasing array).
### Explanation
This approach processes the array in a single pass using a monotonic stack. The stack will store pairs `(value, frequency)`, maintaining values in a non-increasing order from bottom to top. `frequency` tracks how many times a value has appeared in a valid context (i.e., as a block or separated by smaller values).

All single-element subarrays are valid, contributing `n` to the total count. We can handle this by either initializing the count to `n` or by adding 1 for each element inside the loop.

As we iterate through `nums` with the current element `num`:
1. We pop all elements from the stack whose value is less than `num`. These elements are 'blocked' by `num`, meaning they cannot be the maximum in any subarray that extends to include `num`.
2. After popping, if the stack is not empty and the top element's value is equal to `num`, it signifies we have found previous occurrences of `num` that are valid left boundaries for a subarray ending with the current `num`. The number of such new valid subarrays is exactly the frequency stored in the stack for that value. We add this frequency to our total count. We then increment the frequency for the top element to include the current `num`.
3. If the stack is empty or the top element's value is greater than `num`, the current `num` starts a new sequence. We push `(num, 1)` onto the stack.

This process correctly accumulates the count of all valid subarrays of length greater than one. Adding `n` gives the final answer.

```java
import java.util.Stack;

class Solution {
    // Using a helper class for pairs for clarity
    class Pair {
        int value;
        int freq;
        Pair(int value, int freq) {
            this.value = value;
            this.freq = freq;
        }
    }

    public long numberOfSubarrays(int[] nums) {
        Stack<Pair> stack = new Stack<>();
        long count = 0;

        for (int num : nums) {
            // Pop elements smaller than the current number
            while (!stack.isEmpty() && stack.peek().value < num) {
                stack.pop();
            }

            // If stack top has the same value
            if (!stack.isEmpty() && stack.peek().value == num) {
                // The current element forms a valid subarray with each of the previous
                // occurrences of the same value at this stack level.
                // We also count the subarray formed by the element itself.
                count += stack.peek().freq + 1;
                stack.peek().freq++;
            } else {
                // This is a new element sequence or the first element
                // It forms one valid subarray with itself.
                count += 1;
                stack.push(new Pair(num, 1));
            }
        }

        return count;
    }
}
```
### Algorithm
1. Initialize `count = 0` and an empty stack. The stack will store pairs of `(value, frequency)`.
2. Add `n` to the `count` upfront. This accounts for all single-element subarrays, which are always valid.
3. Iterate through the input array `nums` with element `num`.
4. For each `num`, pop elements from the stack while the stack is not empty and the value at the top of the stack is less than `num`.
5. After popping, check the top of the stack:
   a. If the stack is not empty and its top element's value is equal to `num`, it means we have found a block of identical elements separated by smaller elements. The number of new valid subarrays formed is equal to the frequency of this element on the stack. Add this frequency to `count`, and then increment the frequency on the stack.
   b. If the stack is empty or its top element's value is greater than `num`, it means `num` starts a new potential sequence. Push a new pair `(num, 1)` onto the stack.
6. The loop calculates the count for subarrays of length > 1. The initial `n` covers the single-element ones. Return the total `count`.
*Note: The initial count can be `n` and the loop adds counts for pairs, or the initial count can be `0` and the loop logic is slightly adjusted to add `1` for the element itself plus counts for pairs.* The provided code uses the latter.

# Solutions
### Java

```java
class Solution {
public
  long numberOfSubarrays(int[] nums) {
    Deque<int[]> stk = new ArrayDeque<>();
    long ans = 0;
    for (int x : nums) {
      while (!stk.isEmpty() && stk.peek()[0] < x) {
        stk.pop();
      }
      if (stk.isEmpty() || stk.peek()[0] > x) {
        stk.push(new int[]{x, 1});
      } else {
        stk.peek()[1]++;
      }
      ans += stk.peek()[1];
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long numberOfSubarrays(vector<int> &nums) {
    vector<pair<int, int>> stk;
    long long ans = 0;
    for (int x : nums) {
      while (!stk.empty() && stk.back().first < x) {
        stk.pop_back();
      }
      if (stk.empty() || stk.back().first > x) {
        stk.push_back(make_pair(x, 1));
      } else {
        stk.back().second++;
      }
      ans += stk.back().second;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfSubarrays(self, nums: List[int]) -> int: stk = [] ans = 0 for x in nums: while stk and stk[- 1][0] < x: stk . pop() if not stk or stk[- 1][0] > x: stk . append([x, 1]) else: stk[- 1][1] += 1 ans += stk[- 1][1] return ans

```