LeetCode Daily Practice Problem : 2444. Count Subarrays With Fixed Bounds

Problem Statement:

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:

1. The minimum value in the subarray is equal to minK.
2. 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:

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

Constraints:

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

Photo by Daniel Seßler on Unsplash

Intuition:

To efficiently count the number of fixed-bound subarrays, we can use a sliding window approach. By keeping track of the last occurrences of minK and maxK, we can determine the length of the largest subarray that satisfies the given conditions ending at the current position. Then, we accumulate the count of subarrays satisfying the conditions as we move through the array. Different pointers are used in the following way

r : rpointer, which slides using the for loop and we are finding all arrays that end at r and satisfy the condition that all elements are within bound
l : sub-array nums[l:r+1] is the largest subarray that satisfy condition that all elements are within bound
l_min: last time min value was seen on a index
l_max: last time max value was seen on a index

Every time the window has min and max values we can use the difference of l and min(l_min,l_max) to calculate all sub arrays which satisfy the bound conditions

Approach:

1. Initialize pointers l_min and l_max to None, representing the last occurrences of minK and maxK respectively.
2. Initialize pointer l to 0, representing the start of the current subarray.
3. Iterate through the array using a pointer r, representing the end of the current subarray.
4. Update l_min and l_max if the current element equals minK or maxK respectively.
5. If the current element is outside the bounds [minK, maxK], reset l_min, l_max, and move l to r+1.
6. If both l_min and l_max are not None, accumulate the count of subarrays by adding min(l_min, l_max) - l + 1 to the result.
7. Finally, return the accumulated count.

Time Complexity:

The time complexity of this solution is O(N), where N is the length of the nums array. We traverse the array only once.

Space Complexity:

The space complexity of this solution is O(1), as we use only a constant amount of extra space for storing pointers and variables.