Frontend School

Count Subarrays with Bounded Difference

DSA
hard

Count Subarrays with Bounded Difference

Hard
Two Pointers
Sliding Window
Monotonic Deque

Overview

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.

What you need to do / Task

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.

Input & output

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:

  • An integer representing the total count of subarrays nums[i...j] such that max(nums[i...j]) - min(nums[i...j]) <= k.

Clarifications

  • Empty array: If nums is empty, there are no subarrays, so the function should return 0.
  • Single element subarrays: Any subarray containing a single element [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.
  • Large N: The input array nums can be quite large, so an efficient solution (e.g., O(N) time) is expected.

Examples

1

Example 1

Input:

nums = [1, 3, 2], k = 1

Output:

4

Note:

Valid subarrays are: [1], [3], [2], [3,2].

  • [1]: max-min = 0 <= 1
  • [3]: max-min = 0 <= 1
  • [2]: max-min = 0 <= 1
  • [3,2]: max-min = 3-2 = 1 <= 1 Other subarrays like [1,3] (diff=2) or [1,3,2] (diff=2) are invalid.
2

Example 2

Input:

nums = [1, 2, 3, 4], k = 1

Output:

7

Note:

Valid subarrays are:

  • Single elements: [1], [2], [3], [4] (4 subarrays)
  • Two elements: [1,2], [2,3], [3,4] (3 subarrays) Total: 4 + 3 = 7. All other subarrays have a difference greater than 1.
3

Example 3

Input:

nums = [8, 2, 4, 7], k = 5

Output:

7

Note:

Valid subarrays are:

  • Single elements: [8], [2], [4], [7] (4 subarrays)
  • Two elements: [2,4] (diff=2), [4,7] (diff=3) (2 subarrays)
  • Three elements: [2,4,7] (diff=7-2=5) (1 subarray) Total: 4 + 2 + 1 = 7. Other subarrays like [8,2] (diff=6) or [8,2,4] (diff=6) are invalid.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
  • 0 <= k <= 10^9
  • The solution should aim for optimal time complexity, ideally O(N), and reasonable space complexity, ideally O(N) for auxiliary data structures.

Out of scope

  • Input validation beyond the given constraints (e.g., nums containing non-numeric values, k being negative).
  • Handling extremely large numbers that exceed standard 64-bit integer types (assume nums[i] and k fit within standard number types).

What interviewers evaluate

  • Algorithmic Correctness: The solution accurately counts all valid subarrays according to the problem definition.
  • Efficiency: The chosen algorithm demonstrates optimal time complexity (e.g., O(N)) and efficient use of space.
  • Data Structure Proficiency: Effective selection and utilization of appropriate data structures (e.g., monotonic queues/deques) for maintaining window statistics.
  • Edge Case Handling: Correctly addresses scenarios like single-element arrays and k=0.
  • Code Quality: The code is well-structured, readable, and maintainable, reflecting good software engineering practices.

Loading editor...