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

Solve this problem and provide a detailed explanation of your solution, including time and space complexity analysis. Discuss potential edge cases and how your solution handles them. Provide example code with comments.

def count_fixed_bound_subarrays(nums, minK, maxK):
    n = len(nums)
    count = 0
    for i in range(n):
        for j in range(i, n):
            subarray = nums[i:j+1]
            if minK in subarray and maxK in subarray and min(subarray) == minK and max(subarray) == maxK:
                count += 1
    return count


# Example usage:
nums1 = [1, 3, 5, 2, 7, 5]
minK1 = 1
maxK1 = 5
print(f"Example 1: {count_fixed_bound_subarrays(nums1, minK1, maxK1)}")  # Output: 2

nums2 = [1, 1, 1, 1]
minK2 = 1
maxK2 = 1
print(f"Example 2: {count_fixed_bound_subarrays(nums2, minK2, maxK2)}")  # Output: 10

nums3 = [1, 3, 5, 2]
minK3 = 2
maxK3 = 5
print(f"Example 3: {count_fixed_bound_subarrays(nums3, minK3, maxK3)}")  # Output: 1

nums4 = [1, 5, 2, 3, 4]
minK4 = 4
maxK4 = 4
print(f"Example 4: {count_fixed_bound_subarrays(nums4, minK4, maxK4)}")  # Output: 0

Optimal Solution

def count_fixed_bound_subarrays_optimal(nums, minK, maxK):
    n = len(nums)
    count = 0
    left = -1  # Leftmost index of invalid element
    min_idx = -1  # Last seen index of minK
    max_idx = -1  # Last seen index of maxK

    for i in range(n):
        if nums[i] < minK or nums[i] > maxK:
            left = i

        if nums[i] == minK:
            min_idx = i

        if nums[i] == maxK:
            max_idx = i

        if min_idx != -1 and max_idx != -1:
            start = max(left, min(min_idx, max_idx))
            end = min(min_idx, max_idx)
            count += end - left
            if left >= end: #no possible subarrays.
                count = count - (end-left) 

    return count


# Example usage:
nums1 = [1, 3, 5, 2, 7, 5]
minK1 = 1
maxK1 = 5
print(f"Example 1: {count_fixed_bound_subarrays_optimal(nums1, minK1, maxK1)}")  # Output: 2

nums2 = [1, 1, 1, 1]
minK2 = 1
maxK2 = 1
print(f"Example 2: {count_fixed_bound_subarrays_optimal(nums2, minK2, maxK2)}")  # Output: 10

nums3 = [1, 3, 5, 2]
minK3 = 2
maxK3 = 5
print(f"Example 3: {count_fixed_bound_subarrays_optimal(nums3, minK3, maxK3)}")  # Output: 1

nums4 = [1, 5, 2, 3, 4]
minK4 = 4
maxK4 = 4
print(f"Example 4: {count_fixed_bound_subarrays_optimal(nums4, minK4, maxK4)}")  # Output: 0

nums5 = [6, 3, 4, 5, 6, 5, 6, 4, 3]
minK5 = 3
maxK5 = 5
print(f"Example 5: {count_fixed_bound_subarrays_optimal(nums5, minK5, maxK5)}")  # Output: 6

nums6 = [4,3,8,6,4,1,8,8]
minK6 = 1
maxK6 = 8
print(f"Example 6: {count_fixed_bound_subarrays_optimal(nums6, minK6, maxK6)}") # Output 2

nums7 = [7,1,8,4,9,5,7,9,7,8,5,1,4,9,8]
minK7 = 1
maxK7 = 9
print(f"Example 7: {count_fixed_bound_subarrays_optimal(nums7, minK7, maxK7)}") # Output 6

Big(O) Runtime Analysis

Naive Solution:

• The outer loop iterates n times.
• The inner loop iterates up to n times.
• The min and max functions on a subarray take O(k) where k is the length of the subarray.
• Overall time complexity: O(n^3) in the worst case.

Optimal Solution:

• The algorithm iterates through the array once.
• Inside the loop, only constant time operations are performed.
• Overall time complexity: O(n).

Big(O) Space Usage Analysis

Naive Solution:

• Uses a constant amount of extra space.
• Space complexity: O(1).

Optimal Solution:

• Uses a constant amount of extra space to store indices.
• Space complexity: O(1).

Edge Cases

1. Empty Array: If the input array is empty, the function should return 0.
2. minK == maxK: The algorithm should handle the case when minK and maxK are equal. In this case, the subarray must only contain the value minK.
3. minK > maxK: This is an invalid input. The function should ideally handle this by returning 0 or raising an exception, but based on the problem constraints, this scenario might not occur.
4. Array with no fixed-bound subarrays: The algorithm should correctly return 0 when there are no subarrays that satisfy the condition.
5. Large Array: The algorithm should be efficient enough to handle large arrays (up to 10^5 elements as per the constraints).
6. Array with Duplicate Values: If there are duplicate values of minK and maxK in the array, the algorithm should still work correctly.
7. Array where minK or maxK is not present: The function should return 0, if either minK or maxK is not in the array.
8. Subarray of length 1: Single-element subarrays should also be considered. For example, if nums = [5] and minK = 5, maxK = 5, the answer should be 1.
9. All Elements are in Range: The array contains elements that all lie between minK and maxK, but the count should accurately reflect the number of valid subarrays.