Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2444.html

2444. Count Subarrays With Fixed Bounds

  • Difficulty: Hard.
  • Related Topics: .
  • Similar Questions: .

Problem

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 <= 10^5

  • 1 <= nums[i], minK, maxK <= 10^6

Solution (Java, C++, Python)

  • 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)
    }
    
    func min(a, b int) int {
    	if a < b {
    		return a
    	}
    	return b
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
  • 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
        }
    }
    
    

Explain:

nope.

Complexity:

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

All Problems

All Solutions