Find the Number of Subarrays Where Boundary Elements Are Maximum

Hard
1415.

Find the Number of Subarrays Where Boundary Elements Are Maximum

Find the Number of Subarrays Where Boundary Elements Are Maximum is a hard coding problem on arrays, binary search and stack, asked in Amazon and Google interviews.

Given an array of positive integers nums, count the subarrays whose first and last elements are both equal to the largest element of that subarray.

A single element is such a subarray on its own.

(The length bound below is tighter than the original problem's so that the count fits in a 32-bit integer.)

Example 1

Input
nums = [2,5,2,5,1]
Output
6
Explanation
The five single elements, plus `[5,2,5]`. `[2,5,2]` does not count: its largest element is 5.

Example 2

Input
nums = [4,4,4]
Output
6
Explanation
Every subarray qualifies.

Example 3

Input
nums = [3,1,3,1,3]
Output
8
Explanation
Five singles plus `[3,1,3]` twice and the whole array.

Constraints

  • 1 <= nums.length <= 6 * 10^4
  • 1 <= nums[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfSubarrays = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Number of Subarrays Where Boundary Elements Are Maximum

Find the Number of Subarrays Where Boundary Elements Are Maximum solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find the Number of Subarrays Where Boundary Elements Are Maximum is a hard coding problem on arrays, binary search and stack, asked in Amazon and Google interviews.

Problem statement

Given an array of positive integers nums, count the subarrays whose first and last elements are both equal to the largest element of that subarray.

A single element is such a subarray on its own.

(The length bound below is tighter than the original problem's so that the count fits in a 32-bit integer.)

Example 1

Input: nums = [2,5,2,5,1]
Output: 6
Explanation: The five single elements, plus `[5,2,5]`. `[2,5,2]` does not count: its largest element is 5.

Example 2

Input: nums = [4,4,4]
Output: 6
Explanation: Every subarray qualifies.

Example 3

Input: nums = [3,1,3,1,3]
Output: 8
Explanation: Five singles plus `[3,1,3]` twice and the whole array.

Constraints

  • 1 <= nums.length <= 6 * 10^4
  • 1 <= nums[i] <= 10^9

Hints for Find the Number of Subarrays Where Boundary Elements Are Maximum

  1. Hint 1

    Fix the right end j. Which left ends i work? nums[i] must equal nums[j] and nothing between them may be larger.

  2. Hint 2

    So you need, for the current value, how many equal values appear since the last strictly larger value.

  3. Hint 3

    Keep a stack of (value, count) with strictly decreasing values. For x, pop smaller values; if the top equals x, increment its count, otherwise push (x, 1). Add the top's count to the answer.

How to solve Find the Number of Subarrays Where Boundary Elements Are Maximum

A valid subarray ending at j starts at an earlier copy of nums[j] with no larger value in between. A monotonic stack that merges equal values keeps exactly that count for the current value.

Approach

  1. Keep a stack of pairs (value, count) with strictly decreasing values from bottom to top.
  2. For each x: pop while the top's value is smaller than x — those values are now blocked by x forever.
  3. If the top's value equals x, increment its count; otherwise push (x, 1).
  4. The top's count is the number of valid subarrays ending at this position; add it to the answer.

Why it works

After processing position j, the top entry for value nums[j] counts the occurrences of nums[j] since the most recent strictly larger element — any older copy is separated from j by something larger and was removed when that larger value popped it. Each such occurrence is a valid left end, and no other left end is valid, so the per-position additions sum to the answer.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Pop only strictly smaller values; equal values must be merged, not discarded.
  • Each position contributes at least 1 — the single-element subarray.
  • An all-equal array gives n(n+1)/2 subarrays, which is why the length is capped here.

Reference solution

Python

from typing import List

def numberOfSubarrays(nums: List[int]) -> int:
    st = []  # [value, count], values strictly decreasing
    ans = 0
    for x in nums:
        while st and st[-1][0] < x:
            st.pop()
        if st and st[-1][0] == x:
            st[-1][1] += 1
        else:
            st.append([x, 1])
        ans += st[-1][1]
    return ans

Java

public static int numberOfSubarrays(int[] nums) {
    int n = nums.length;
    int[] vals = new int[n], cnts = new int[n];
    int top = 0;
    long ans = 0;
    for (int x : nums) {
        while (top > 0 && vals[top - 1] < x) top--;
        if (top > 0 && vals[top - 1] == x) {
            cnts[top - 1]++;
        } else {
            vals[top] = x;
            cnts[top] = 1;
            top++;
        }
        ans += cnts[top - 1];
    }
    return (int) ans;
}

C++

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

JavaScript

var numberOfSubarrays = function(nums) {
    var vals = [], cnts = [];
    var ans = 0;
    for (var i = 0; i < nums.length; i++) {
        var x = nums[i];
        while (vals.length > 0 && vals[vals.length - 1] < x) { vals.pop(); cnts.pop(); }
        if (vals.length > 0 && vals[vals.length - 1] === x) {
            cnts[cnts.length - 1]++;
        } else {
            vals.push(x);
            cnts.push(1);
        }
        ans += cnts[cnts.length - 1];
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search