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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Valid Subarrays

Number: 1061

Difficulty: Hard

Paid? Yes

Companies: Amazon, Hulu

Problem Description

Given an integer array nums, return the number of non-empty subarrays where the leftmost element is not larger than any other element in that subarray. In other words, for a subarray [nums[i], nums[i+1], …, nums[j]], the condition nums[i] <= nums[k] for all i ≤ k ≤ j must hold.

Key Insights

  • Every valid subarray starts at an index i and can be extended until an element smaller than nums[i] is encountered.
  • The number of valid subarrays starting at index i equals the distance from i to the first index where nums[k] < nums[i] (or the end of the array if no such element exists).
  • A monotonic (non-decreasing) stack can be used to efficiently compute the first index to the right where the subarray condition fails, achieving a linear time solution.
  • Precomputing these boundaries avoids a potential O(n^2) solution and scales efficiently for the maximum constraints.

Space and Time Complexity

Time Complexity: O(n) – Each element is pushed and popped at most once from the stack. Space Complexity: O(n) – The stack may store up to n elements in the worst case.

Solution

We iterate through the array from right to left and use a monotonic stack to record the next index where the element is strictly smaller than the current element. For index i, if such an index j is found, then the number of valid subarrays starting at i is (j - i). If no smaller element is found, the count is (n - i), where n is the length of the array. Summing these counts over all indices gives the final answer.

The key trick is to use the monotonic stack so that we efficiently "jump" to the first violation for each starting index, which avoids checking every possibility explicitly.

Code Solutions

# Python solution for Number of Valid Subarrays

def validSubarrays(nums):
    n = len(nums)
    result = 0
    stack = []  # stack to store indices of elements in non-decreasing order
    
    # iterate from rightmost element to leftmost
    for i in range(n - 1, -1, -1):
        # pop from stack until the current element is <= element at top of stack
        while stack and nums[i] > nums[stack[-1]]:
            stack.pop()
        
        # if stack is empty, no smaller element exists to the right
        if not stack:
            valid_count = n - i
        else:
            # the first index with an element < nums[i] is stack[-1]
            valid_count = stack[-1] - i
            
        result += valid_count
        
        # push current index onto stack
        stack.append(i)
    
    return result

# Example usage:
print(validSubarrays([1,4,2,5,3]))  # Output: 11
print(validSubarrays([3,2,1]))      # Output: 3
print(validSubarrays([2,2,2]))      # Output: 6
← Back to All Questions