2444. Count Subarrays With Fixed Bounds - Detailed Explanation

Problem Statement

Description:
You are given an integer array nums and two integers minK and maxK. A fixed-bound subarray of nums is a contiguous 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.
• Every element in the subarray lies between minK and maxK (inclusive).

Return the number of fixed-bound subarrays.

Examples:

• Example 1:

  • Input: nums = [1, 3, 5, 2, 7, 5], minK = 1, maxK = 5
  • Output: 2
  • Explanation:
    The valid subarrays are:
    1. [1, 3, 5]
    2. [1, 3, 5, 2]
       Other subarrays either do not contain both 1 and 5 or contain elements outside the range [1, 5].

• Example 2:

  • Input: nums = [1, 1, 1, 1], minK = 1, maxK = 1
  • Output: 10
  • Explanation:
    Since minK and maxK are both 1, every subarray (and there are 10 total in an array of length 4) is valid.

• Example 3:

  • Input: nums = [2, 3, 4], minK = 1, maxK = 5
  • Output: 0
  • Explanation:
    There is no occurrence of minK (1) in the array, so no subarray qualifies.

Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i], minK, maxK <= 10^9

Hints Before You Start

• Hint 1: Think about how to efficiently count subarrays by processing the array in one pass rather than checking every possible subarray.
• Hint 2: Consider tracking the most recent positions where minK and maxK occurred as well as the last index where an invalid element (outside the range [minK, maxK]) was encountered.

Approaches

Brute Force Approach

Idea:

• Enumerate every possible subarray of nums and check if it meets the conditions (i.e., contains at least one minK, one maxK, and no elements outside the range [minK, maxK]).

Steps:

1. Iterate over all possible starting indices.
2. For each starting index, extend the subarray and check:
   • Whether both minK and maxK are present.
   • Whether every element lies within the valid range.
3. Count the subarrays that satisfy these conditions.

Complexity Analysis:

• Time Complexity: O(n²) or worse, since there are O(n²) subarrays to check and each check might be O(n) in the worst case.
• Space Complexity: O(1) (ignoring the space needed to store the input).

Drawbacks:

• The brute force solution is not practical for large inputs (n up to 10^5).

Optimal Approach (Using a Single Pass with Pointers)

Idea:

• Process the array in one pass while maintaining:
  • lastInvalid: The last index where an element was outside the range [minK, maxK]. Any subarray that crosses this index is invalid.
  • lastMin: The most recent index where nums[i] was equal to minK.
  • lastMax: The most recent index where nums[i] was equal to maxK.
• For each index i, if both lastMin and lastMax are valid (i.e. greater than lastInvalid), then the number of valid subarrays ending at i is determined by the earliest occurrence between lastMin and lastMax relative to lastInvalid.

Detailed Steps:

1. Initialize:

   • lastInvalid = -1
   • lastMin = -1
   • lastMax = -1
   • result = 0

2. Iterate over the array (index i):

   • Step A: If nums[i] is less than minK or greater than maxK, update lastInvalid = i because the current element invalidates any subarray containing it.
   • Step B: If nums[i] == minK, update lastMin = i.
   • Step C: If nums[i] == maxK, update lastMax = i.
   • Step D: The current index can form valid subarrays if both lastMin and lastMax are greater than lastInvalid.
     Calculate count = max(0, min(lastMin, lastMax) - lastInvalid).
     This number represents how many starting positions (after the last invalid index) can form a valid subarray ending at i.
   • Step E: Add count to result.

3. Return:

   • The total count result.

Visual Example:

For nums = [1, 3, 5, 2, 7, 5], minK = 1, maxK = 5:

• Initialization:
  lastInvalid = -1, lastMin = -1, lastMax = -1, result = 0

• i = 0 (value 1):

  • nums[0] equals minK, so lastMin = 0.
  • No update for lastMax.
  • min(lastMin, lastMax) is undefined (because lastMax == -1), so no valid subarray ending at index 0.

• i = 1 (value 3):

  • 3 is within [1, 5] but not equal to either bound.
  • No update for lastMin or lastMax.
  • Still no valid subarray since lastMax is -1.

• i = 2 (value 5):

  • nums[2] equals maxK, so lastMax = 2.
  • Now, both lastMin (0) and lastMax (2) are valid, and both > lastInvalid (-1).
  • Valid subarrays ending at index 2: count = min(0, 2) - (-1) = 0 - (-1) = 1
    → The valid subarray is [1, 3, 5].
  • result becomes 1.

• i = 3 (value 2):

  • 2 is valid (in range).
  • No updates to lastMin or lastMax.
  • Count = min(lastMin, lastMax) - lastInvalid = min(0, 2) - (-1) = 0 - (-1) = 1
    → The valid subarray ending at index 3 is still determined by the position of 1 (since min(lastMin, lastMax) remains 0), forming [1, 3, 5, 2].
  • result becomes 2.

• i = 4 (value 7):

  • 7 is outside the range [1, 5], update lastInvalid = 4.
  • This resets the potential for valid subarrays until a new minK or maxK is seen after index 4.

• i = 5 (value 5):

  • nums[5] equals maxK, so lastMax = 5.
  • lastMin remains at 0 but note that index 0 is before lastInvalid.
  • Since lastMin (0) ≤ lastInvalid (4), no valid subarray ending at index 5 can be formed.
  • result remains 2.

Complexity Analysis:

• Time Complexity: O(n), as we process each element exactly once.
• Space Complexity: O(1), only using a few variables for tracking indices.

Code Implementations

Python Code (Optimal Approach)