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: Sliding Window

• Time complexity: O(n)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} minK
 * @param {number} maxK
 * @return {number}
 */
const countSubarrays = function (nums, minK, maxK) {
  const n = nums.length;
  let prevMinK = -1;
  let prevMaxK = -1;
  let left = -1;
  let result = 0;

  for (let index = 0; index < n; index++) {
    const num = nums[index];

    if (num < minK || num > maxK) {
      left = index;
    }

    if (num === minK) {
      prevMinK = index;
    }

    if (num === maxK) {
      prevMaxK = index;
    }

    const count = Math.max(0, Math.min(prevMinK, prevMaxK) - left);

    result += count;
  }

  return result;
};