We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Number of Subarrays Where Boundary Elements Are Maximum

Number: 3382

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given an array of positive integers nums, count how many non‐empty contiguous subarrays satisfy the following property: if m is the maximum element in the subarray, then both the first and the last element of the subarray equal m. (Note that a single‐element subarray always qualifies.) For example, for nums = [1,4,3,3,2] the answer is 6.

Key Insights

  • A valid subarray is one in which the maximum element (say v) appears at both ends.
  • For a subarray [i...j] with nums[i] = nums[j] = v to be valid, every element between i and j must be <= v. In other words, no element strictly greater than v appears in the range.
  • It is “local” in the sense that if we know, for each index i, the index NG[i] of the first element to its right that is greater than nums[i] (or NG[i] = n if none exists), then any later occurrence j of the same value v (with j < NG[i]) will guarantee that the maximum in the window i…j is v.
  • Every index forms a valid subarray of length 1. In addition, for every valid pair (i,j) with i < j and nums[i] = nums[j] and j < NG[i], the subarray [i…j] is valid.
  • We can group together indices with the same value and, for each occurrence, count how many later occurrences (within the group) occur before the next greater element (as computed by NG).

Space and Time Complexity

Time Complexity: O(n log n)
 • O(n) to compute the next greater index for every element
 • Plus, grouping indices and doing binary searches on each group (the total number of binary searches is O(n))
Space Complexity: O(n)
 • For the next‐greater array and for storing groups of indices

Solution

The main idea is to “pre‐process” the array by computing, for every index i, the index NG[i] which is the first index j > i such that nums[j] > nums[i] (or NG[i] = n if none exists). For any valid pair of positions i and j (with i < j) that have the same value v, if j < NG[i] then no element in between can “ruin” the window – the subarray [i…j] has maximum v. We group the indices by their value. In each group (which is sorted in increasing order of index) for a given value v, for each occurrence at index i we binary–search within the group to count how many later indices (say j) satisfy j < NG[i]. Finally, we add the number of single–element subarrays (which is n) to get the answer.

The important “gotcha” is to recognize that even if two indices with the same value appear far apart, they only “pair up” if no element in between is greater than that value. The next–greater pre–processing and per–group binary searches ensure that.

Code Solutions

# Python solution
import bisect

def countSubarrays(nums):
    n = len(nums)
    # Compute next greater element indices NG: for index i, NG[i] is the index of the first element > nums[i]
    NG = [n] * n
    stack = []  # will store indices in decreasing order of nums[]
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            idx = stack.pop()
            NG[idx] = i
        stack.append(i)
    
    # Group indices by their value.
    groups = {}
    for i, num in enumerate(nums):
        groups.setdefault(num, []).append(i)
    
    count = 0
    # For each group with the same value, count pairs (i,j) such that j appears after i and j < NG[i].
    for value, indices in groups.items():
        # indices is sorted in increasing order since we traversed nums in order.
        for pos, idx in enumerate(indices):
            # Using binary search find the first position in indices where the index >= NG[idx].
            # All positions from pos+1 up to this found index have j < NG[idx].
            j_pos = bisect.bisect_left(indices, NG[idx], lo=pos+1)
            count += (j_pos - (pos+1))
    
    # Every single-element subarray qualifies.
    return count + n

# Example usage:
nums1 = [1,4,3,3,2]
print(countSubarrays(nums1))  # Expected output: 6
← Back to All Questions