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).