Welcome to Subscribe On Youtube

795. Number of Subarrays with Bounded Maximum

Description

Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the value of the maximum array element in that subarray is in the range [left, right].

The test cases are generated so that the answer will fit in a 32-bit integer.

 

Example 1:

Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Example 2:

Input: nums = [2,9,2,5,6], left = 2, right = 8
Output: 7

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= left <= right <= 109

Solutions

• Java
• C++
• Python
• Go
• Java 2
• C++ 2
• Python 2
• Go 2

• class Solution {
      public int numSubarrayBoundedMax(int[] nums, int left, int right) {
          return f(nums, right) - f(nums, left - 1);
      }
  
      private int f(int[] nums, int x) {
          int cnt = 0, t = 0;
          for (int v : nums) {
              t = v > x ? 0 : t + 1;
              cnt += t;
          }
          return cnt;
      }
  }
  

• class Solution {
  public:
      int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
          auto f = [&](int x) {
              int cnt = 0, t = 0;
              for (int& v : nums) {
                  t = v > x ? 0 : t + 1;
                  cnt += t;
              }
              return cnt;
          };
          return f(right) - f(left - 1);
      }
  };
  

• class Solution:
      def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
          def f(x):
              cnt = t = 0
              for v in nums:
                  t = 0 if v > x else t + 1
                  cnt += t
              return cnt
  
          return f(right) - f(left - 1)
  
  

• func numSubarrayBoundedMax(nums []int, left int, right int) int {
  	f := func(x int) (cnt int) {
  		t := 0
  		for _, v := range nums {
  			t++
  			if v > x {
  				t = 0
  			}
  			cnt += t
  		}
  		return
  	}
  	return f(right) - f(left-1)
  }
  

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

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

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

• func numSubarrayBoundedMax(nums []int, left int, right int) (ans int) {
  	n := len(nums)
  	l := make([]int, n)
  	r := make([]int, n)
  	for i := range l {
  		l[i], r[i] = -1, n
  	}
  	stk := []int{}
  	for i, v := range nums {
  		for len(stk) > 0 && nums[stk[len(stk)-1]] <= v {
  			stk = stk[:len(stk)-1]
  		}
  		if len(stk) > 0 {
  			l[i] = stk[len(stk)-1]
  		}
  		stk = append(stk, i)
  	}
  	stk = []int{}
  	for i := n - 1; i >= 0; i-- {
  		v := nums[i]
  		for len(stk) > 0 && nums[stk[len(stk)-1]] < v {
  			stk = stk[:len(stk)-1]
  		}
  		if len(stk) > 0 {
  			r[i] = stk[len(stk)-1]
  		}
  		stk = append(stk, i)
  	}
  	for i, v := range nums {
  		if left <= v && v <= right {
  			ans += (i - l[i]) * (r[i] - i)
  		}
  	}
  	return
  }
  

All Problems

All Solutions