1063

1063. Number of Valid Subarrays (Hard)

Given an integer array nums, return the number of non-empty subarrays with the leftmost element of the subarray not larger than other elements in the subarray.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

Example 2:

Input: nums = [3,2,1]
Output: 3
Explanation: The 3 valid subarrays are: [3],[2],[1].

Example 3:

Input: nums = [2,2,2]
Output: 6
Explanation: There are 6 valid subarrays: [2],[2],[2],[2,2],[2,2],[2,2,2].

 

Constraints:

• 1 <= nums.length <= 5 * 104
• 0 <= nums[i] <= 105

Companies: Hulu

Related Topics:
Array, Stack, Monotonic Stack

Similar Questions:

• Number of Smooth Descent Periods of a Stock (Medium)

Hints:

• Given a data structure that answers queries of the type to find the minimum in a range of an array (Range minimum query (RMQ) sparse table) in O(1) time. How can you solve this problem?
• For each starting index do a binary search with an RMQ to find the ending possible position.

Solution 1.

nextSmaller[i] points to the next smaller element than A[i].

The time complexity is O(N) because each nextSmaller[i] is visited at most once.

// OJ: https://leetcode.com/problems/number-of-valid-subarrays
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int validSubarrays(vector<int>& A) {
        int N = A.size(), ans = 0;
        vector<int> nextSmaller(N, N);
        for (int i = N - 1; i >= 0; --i) {
            int j = i + 1;
            while (j < N && A[j] >= A[i]) j = nextSmaller[j];
            nextSmaller[i] = j;
            ans += j - i;
        }
        return ans;
    }
};