Welcome to Subscribe On Youtube

2444. Count Subarrays With Fixed Bounds

Description

You are given an integer array nums and two integers minK and maxK.

A fixed-bound subarray of nums is a subarray that satisfies the following conditions:

• The minimum value in the subarray is equal to minK.
• The maximum value in the subarray is equal to maxK.

Return the number of fixed-bound subarrays.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Output: 2
Explanation: The fixed-bound subarrays are [1,3,5] and [1,3,5,2].

Example 2:

Input: nums = [1,1,1,1], minK = 1, maxK = 1
Output: 10
Explanation: Every subarray of nums is a fixed-bound subarray. There are 10 possible subarrays.

 

Constraints:

• 2 <= nums.length <= 105
• 1 <= nums[i], minK, maxK <= 106

Solutions

Solution 1: Enumeration of Right Endpoint

From the problem description, we know that all elements of the bounded subarray are in the interval [minK, maxK], and the minimum value must be minK, and the maximum value must be maxK.

We traverse the array $nums$, count the number of bounded subarrays with nums[i] as the right endpoint, and then add all the counts.

The specific implementation logic is as follows:

1. Maintain the index $k$ of the most recent element not in the interval [minK, maxK], initially set to $-1$. Therefore, the left endpoint of the current element nums[i] must be greater than $k$.
2. Maintain the index $j_1$ of the most recent element with a value of minK, and the index $j_2$ of the most recent element with a value of maxK, both initially set to $-1$. Therefore, the left endpoint of the current element nums[i] must be less than or equal to $min(j_1,j_2)$.
3. In summary, the number of bounded subarrays with the current element as the right endpoint is $max(0,min(j_1,j_2)-k)$. Add up all the counts to get the result.

The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array $nums$.

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

• class Solution {
      public long countSubarrays(int[] nums, int minK, int maxK) {
          long ans = 0;
          int j1 = -1, j2 = -1, k = -1;
          for (int i = 0; i < nums.length; ++i) {
              if (nums[i] < minK || nums[i] > maxK) {
                  k = i;
              }
              if (nums[i] == minK) {
                  j1 = i;
              }
              if (nums[i] == maxK) {
                  j2 = i;
              }
              ans += Math.max(0, Math.min(j1, j2) - k);
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      long long countSubarrays(vector<int>& nums, int minK, int maxK) {
          long long ans = 0;
          int j1 = -1, j2 = -1, k = -1;
          for (int i = 0; i < nums.size(); ++i) {
              if (nums[i] < minK || nums[i] > maxK) k = i;
              if (nums[i] == minK) j1 = i;
              if (nums[i] == maxK) j2 = i;
              ans += max(0, min(j1, j2) - k);
          }
          return ans;
      }
  };
  

• class Solution:
      def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
          j1 = j2 = k = -1
          ans = 0
          for i, v in enumerate(nums):
              if v < minK or v > maxK:
                  k = i
              if v == minK:
                  j1 = i
              if v == maxK:
                  j2 = i
              ans += max(0, min(j1, j2) - k)
          return ans
  
  

• func countSubarrays(nums []int, minK int, maxK int) int64 {
  	ans := 0
  	j1, j2, k := -1, -1, -1
  	for i, v := range nums {
  		if v < minK || v > maxK {
  			k = i
  		}
  		if v == minK {
  			j1 = i
  		}
  		if v == maxK {
  			j2 = i
  		}
  		ans += max(0, min(j1, j2)-k)
  	}
  	return int64(ans)
  }
  

• function countSubarrays(nums: number[], minK: number, maxK: number): number {
      let res = 0;
      let minIndex = -1;
      let maxIndex = -1;
      let k = -1;
      nums.forEach((num, i) => {
          if (num === minK) {
              minIndex = i;
          }
          if (num === maxK) {
              maxIndex = i;
          }
          if (num < minK || num > maxK) {
              k = i;
          }
          res += Math.max(Math.min(minIndex, maxIndex) - k, 0);
      });
      return res;
  }
  
  

• impl Solution {
      pub fn count_subarrays(nums: Vec<i32>, min_k: i32, max_k: i32) -> i64 {
          let mut res = 0;
          let mut min_index = -1;
          let mut max_index = -1;
          let mut k = -1;
          for i in 0..nums.len() {
              let num = nums[i];
              let i = i as i64;
              if num == min_k {
                  min_index = i;
              }
              if num == max_k {
                  max_index = i;
              }
              if num < min_k || num > max_k {
                  k = i;
              }
              res += (0).max(min_index.min(max_index) - k);
          }
          res
      }
  }
  
  

All Problems

All Solutions