Subarray: March-POTD

Day 7/75:

Question: Count Subarrays With Fixed Bounds -(Hard)

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.

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

Intuition: Problem of counting fixed-bound subarrays within an array nums, our intuition leads us to a brute force approach.

We begin by exploring every possible subarray and checking if it satisfies the conditions of having the minimum value equal to minK and the maximum value equal to maxK. However, the potential inefficiency of this approach, especially for larger input sizes. Hence, we tried to think of optimized solutions that offer better time and space complexity.

Brute Force Approach: The brute force approach involves examining every possible subarray within the array nums and verifying if it meets the fixed-bound subarray condition. We iterate through all possible subarrays, track their minimum and maximum values, and increment the count if they match minK and maxK. While this approach provides a straightforward solution, its time complexity can be high, especially for larger arrays.

Optimized Approach: In this approach, we iterate through the nums array and maintain three variables: minPos, maxPos, and wrongIndex.

These variables keep track of the positions of the minimum value (minK), the maximum value (maxK), and the index of the last element outside the range [minK, maxK], respectively.

Using these positions, we calculate the count of fixed-bound subarrays and increment the ans variable accordingly. Finally, we return the total count of fixed-bound subarrays.

Code:

Time Complexity: O(n), where n represents the length of the input array nums. as traversing all array elements only once.

Space Complexity: O(1), as it requires only a fixed amount of additional space for variables regardless of input size.