Count Subarrays with Bounded Difference
Pinterest's platform thrives on high-quality, relevant content. Imagine we're analyzing the "aesthetic score" of pins within a curated board or a sequence of user interactions. We want to identify contiguous segments where the variation in aesthetic scores (or any other numerical attribute) is "stable" or "consistent". This problem asks you to count the number of such segments (subarrays) where the difference between the maximum and minimum values within the segment does not exceed a given threshold k.
Implement a function countBoundedSubarrays that takes an array of integers nums and an integer k. Your task is to return the total count of non-empty subarrays [i, j] (where 0 <= i <= j < nums.length) such that the difference between the maximum and minimum elements within nums[i...j] is less than or equal to k.
Function Signature:
function countBoundedSubarrays(nums: number[], k: number): number
nums: An array of integers representing the sequence of values.k: A non-negative integer representing the maximum allowed difference between the maximum and minimum elements in a valid subarray.Return Value:
nums[i...j] such that max(nums[i...j]) - min(nums[i...j]) <= k.nums is empty, there are no subarrays, so the function should return 0.[x] will always have max(x) - min(x) = 0, which is <= k for any non-negative k. These should be counted.k = 0: Only subarrays where all elements are identical will be counted.N: The input array nums can be quite large, so an efficient solution (e.g., O(N) time) is expected.Examples
Example 1
Input:
nums = [1, 3, 2], k = 1
Output:
4
Note:
Valid subarrays are: [1], [3], [2], [3,2].
Example 2
Input:
nums = [1, 2, 3, 4], k = 1
Output:
7
Note:
Valid subarrays are:
Example 3
Input:
nums = [8, 2, 4, 7], k = 5
Output:
7
Note:
Valid subarrays are:
Constraints
1 <= nums.length <= 10^50 <= nums[i] <= 10^90 <= k <= 10^9nums containing non-numeric values, k being negative).nums[i] and k fit within standard number types).k=0.Loading editor...