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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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 <= 10^5
  • 1 <= nums[i] <= 10^9

Solution

Method 1 – Monotonic Stack and Group Counting

Intuition

The key is that for a subarray to be valid, its first and last elements must be the maximum in the subarray. This only happens when all elements between two equal maximums are strictly less than that maximum. So, for each group of consecutive equal maximums, we can count the number of valid subarrays by considering the distance to the next greater element on both sides.

Approach

  1. For each element, find the next greater element to the left and right using a monotonic stack.
  2. For each group of consecutive equal maximums, count the number of subarrays where the group forms the boundary and all elements in between are less.
  3. For each occurrence of the maximum, calculate the number of valid subarrays using the distances to the next greater elements.
  4. Sum up the counts for all such groups.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    long long numberOfSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<int> l(n, -1), r(n, n);
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && nums[st.top()] < nums[i]) {
                r[st.top()] = i;
                st.pop();
            }
            st.push(i);
        }
        while (!st.empty()) st.pop();
        for (int i = n - 1; i >= 0; --i) {
            while (!st.empty() && nums[st.top()] <= nums[i]) {
                l[st.top()] = i;
                st.pop();
            }
            st.push(i);
        }
        long long ans = 0;
        for (int i = 0; i < n;) {
            int j = i;
            while (j < n && nums[j] == nums[i]) ++j;
            for (int k = i; k < j; ++k) {
                long long left = k - l[k];
                long long right = r[k] - k;
                ans += left * right;
            }
            i = j;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

func numberOfSubarrays(nums []int) int64 {
    n := len(nums)
    l := make([]int, n)
    r := make([]int, n)
    for i := range l {
        l[i] = -1
        r[i] = n
    }
    st := []int{}
    for i := 0; i < n; i++ {
        for len(st) > 0 && nums[st[len(st)-1]] < nums[i] {
            r[st[len(st)-1]] = i
            st = st[:len(st)-1]
        }
        st = append(st, i)
    }
    st = []int{}
    for i := n - 1; i >= 0; i-- {
        for len(st) > 0 && nums[st[len(st)-1]] <= nums[i] {
            l[st[len(st)-1]] = i
            st = st[:len(st)-1]
        }
        st = append(st, i)
    }
    var ans int64
    for i := 0; i < n; {
        j := i
        for j < n && nums[j] == nums[i] {
            j++
        }
        for k := i; k < j; k++ {
            left := int64(k - l[k])
            right := int64(r[k] - k)
            ans += left * right
        }
        i = j
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    public long numberOfSubarrays(int[] nums) {
        int n = nums.length;
        int[] l = new int[n], r = new int[n];
        Arrays.fill(l, -1);
        Arrays.fill(r, n);
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            while (!st.isEmpty() && nums[st.peek()] < nums[i]) {
                r[st.pop()] = i;
            }
            st.push(i);
        }
        st.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!st.isEmpty() && nums[st.peek()] <= nums[i]) {
                l[st.pop()] = i;
            }
            st.push(i);
        }
        long ans = 0;
        for (int i = 0; i < n;) {
            int j = i;
            while (j < n && nums[j] == nums[i]) ++j;
            for (int k = i; k < j; ++k) {
                long left = k - l[k];
                long right = r[k] - k;
                ans += left * right;
            }
            i = j;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    fun numberOfSubarrays(nums: IntArray): Long {
        val n = nums.size
        val l = IntArray(n) { -1 }
        val r = IntArray(n) { n }
        val st = ArrayDeque<Int>()
        for (i in 0 until n) {
            while (st.isNotEmpty() && nums[st.last()] < nums[i]) {
                r[st.removeLast()] = i
            }
            st.addLast(i)
        }
        st.clear()
        for (i in n - 1 downTo 0) {
            while (st.isNotEmpty() && nums[st.last()] <= nums[i]) {
                l[st.removeLast()] = i
            }
            st.addLast(i)
        }
        var ans = 0L
        var i = 0
        while (i < n) {
            var j = i
            while (j < n && nums[j] == nums[i]) j++
            for (k in i until j) {
                val left = k - l[k]
                val right = r[k] - k
                ans += left.toLong() * right.toLong()
            }
            i = j
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def numberOfSubarrays(self, nums: list[int]) -> int:
        n = len(nums)
        l = [-1] * n
        r = [n] * n
        st = []
        for i in range(n):
            while st and nums[st[-1]] < nums[i]:
                r[st.pop()] = i
            st.append(i)
        st.clear()
        for i in range(n - 1, -1, -1):
            while st and nums[st[-1]] <= nums[i]:
                l[st.pop()] = i
            st.append(i)
        ans = 0
        i = 0
        while i < n:
            j = i
            while j < n and nums[j] == nums[i]:
                j += 1
            for k in range(i, j):
                left = k - l[k]
                right = r[k] - k
                ans += left * right
            i = j
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

impl Solution {
    pub fn number_of_subarrays(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut l = vec![-1; n];
        let mut r = vec![n as i32; n];
        let mut st = Vec::new();
        for i in 0..n {
            while let Some(&top) = st.last() {
                if nums[top] < nums[i] {
                    r[top] = i as i32;
                    st.pop();
                } else {
                    break;
                }
            }
            st.push(i);
        }
        st.clear();
        for i in (0..n).rev() {
            while let Some(&top) = st.last() {
                if nums[top] <= nums[i] {
                    l[top] = i as i32;
                    st.pop();
                } else {
                    break;
                }
            }
            st.push(i);
        }
        let mut ans = 0i64;
        let mut i = 0;
        while i < n {
            let mut j = i;
            while j < n && nums[j] == nums[i] {
                j += 1;
            }
            for k in i..j {
                let left = (k as i32 - l[k]) as i64;
                let right = (r[k] - k as i32) as i64;
                ans += left * right;
            }
            i = j;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    numberOfSubarrays(nums: number[]): number {
        const n = nums.length;
        const l = Array(n).fill(-1);
        const r = Array(n).fill(n);
        const st: number[] = [];
        for (let i = 0; i < n; ++i) {
            while (st.length && nums[st[st.length - 1]] < nums[i]) {
                r[st.pop()!] = i;
            }
            st.push(i);
        }
        st.length = 0;
        for (let i = n - 1; i >= 0; --i) {
            while (st.length && nums[st[st.length - 1]] <= nums[i]) {
                l[st.pop()!] = i;
            }
            st.push(i);
        }
        let ans = 0;
        let i = 0;
        while (i < n) {
            let j = i;
            while (j < n && nums[j] === nums[i]) ++j;
            for (let k = i; k < j; ++k) {
                const left = k - l[k];
                const right = r[k] - k;
                ans += left * right;
            }
            i = j;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Each element is pushed and popped from the stack at most once, and the final pass is linear.
  • 🧺 Space complexity: O(n) — For the left/right arrays and the stack.