Welcome to Subscribe On Youtube

1063. Number of Valid Subarrays

Description

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

Solutions

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int validSubarrays(int[] nums) {
          int n = nums.length;
          int[] right = new int[n];
          Arrays.fill(right, n);
          Deque<Integer> stk = new ArrayDeque<>();
          for (int i = n - 1; i >= 0; --i) {
              while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) {
                  stk.pop();
              }
              if (!stk.isEmpty()) {
                  right[i] = stk.peek();
              }
              stk.push(i);
          }
          int ans = 0;
          for (int i = 0; i < n; ++i) {
              ans += right[i] - i;
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int validSubarrays(vector<int>& nums) {
          int n = nums.size();
          vector<int> right(n, n);
          stack<int> stk;
          for (int i = n - 1; ~i; --i) {
              while (stk.size() && nums[stk.top()] >= nums[i]) {
                  stk.pop();
              }
              if (stk.size()) {
                  right[i] = stk.top();
              }
              stk.push(i);
          }
          int ans = 0;
          for (int i = 0; i < n; ++i) {
              ans += right[i] - i;
          }
          return ans;
      }
  };
  

• class Solution:
      def validSubarrays(self, nums: List[int]) -> int:
          n = len(nums)
          right = [n] * n
          stk = []
          for i in range(n - 1, -1, -1):
              while stk and nums[stk[-1]] >= nums[i]:
                  stk.pop()
              if stk:
                  right[i] = stk[-1]
              stk.append(i)
          return sum(j - i for i, j in enumerate(right))
  
  

• func validSubarrays(nums []int) (ans int) {
  	n := len(nums)
  	right := make([]int, n)
  	for i := range right {
  		right[i] = n
  	}
  	stk := []int{}
  	for i := n - 1; i >= 0; i-- {
  		for len(stk) > 0 && nums[stk[len(stk)-1]] >= nums[i] {
  			stk = stk[:len(stk)-1]
  		}
  		if len(stk) > 0 {
  			right[i] = stk[len(stk)-1]
  		}
  		stk = append(stk, i)
  	}
  	for i, j := range right {
  		ans += j - i
  	}
  	return
  }
  

• function validSubarrays(nums: number[]): number {
      const n = nums.length;
      const right: number[] = Array(n).fill(n);
      const stk: number[] = [];
      for (let i = n - 1; ~i; --i) {
          while (stk.length && nums[stk.at(-1)] >= nums[i]) {
              stk.pop();
          }
          if (stk.length) {
              right[i] = stk.at(-1)!;
          }
          stk.push(i);
      }
      let ans = 0;
      for (let i = 0; i < n; ++i) {
          ans += right[i] - i;
      }
      return ans;
  }
  
  

All Problems

All Solutions