Count Subarrays Between Min and Max

Count Fixed-Bound Subarrays — Satisfying MinK and MaxK

Problem Statement

You are given an array of integers 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.

Your task is to return the number of fixed-bound subarrays in nums.

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

Best Technique – Sliding Window + Boundary Tracking

This problem can be tricky because you need to ensure the subarray contains both the minimum and maximum values exactly. We can efficiently solve this using a sliding window technique, maintaining boundaries to ensure that the subarrays stay valid.

Different Approaches:

Approach 1: Brute Force with Set Tracking

We could try every possible subarray and check if it meets the conditions. This involves using a Set to track the minimum and maximum values of each subarray. If the subarray contains both minK and maxK, we count it.

public static int countFixedBoundSubarrays(int[] nums, int minK, int maxK) {
    int n = nums.length;
    int result = 0;

    for (int i = 0; i < n; i++) {
        Set<Integer> seen = new HashSet<>();
        for (int j = i; j < n; j++) {
            seen.add(nums[j]);
            if (seen.contains(minK) && seen.contains(maxK)) {
                result++;
            }
        }
    }
    return result;
}

Approach 2: HashMap with Frequency Counting (Improved Brute Force)

To optimize the brute force solution, we can use a HashMap to keep track of element frequencies in the subarray. This way, we don’t need to recompute the set for every subarray from scratch.

public static int countFixedBoundSubarraysWithMap(int[] nums, int minK, int maxK) {
    int result = 0;
    
    for (int i = 0; i < nums.length; i++) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int j = i; j < nums.length; j++) {
            freq.put(nums[j], freq.getOrDefault(nums[j], 0) + 1);
            if (freq.containsKey(minK) && freq.containsKey(maxK)) {
                result++;
            }
        }
    }

    return result;
}

Approach 3: Optimized Sliding Window with Boundary Tracking

Instead of checking every subarray, we can maintain a sliding window that dynamically checks for valid subarrays. We'll use two variables left and right to define the window, and track the number of valid subarrays as the window expands and contracts.

public static int countFixedBoundSubarraysOptimized(int[] nums, int minK, int maxK) {
    int result = 0;
    int left = 0;
    int lastMinK = -1;
    int lastMaxK = -1;
    int n = nums.length;
    
    for (int right = 0; right < n; right++) {
        if (nums[right] < minK || nums[right] > maxK) {
            left = right + 1; // Reset the window
            continue;
        }
        
        if (nums[right] == minK) lastMinK = right;
        if (nums[right] == maxK) lastMaxK = right;
        
        if (lastMinK != -1 && lastMaxK != -1) {
            result += Math.min(lastMinK, lastMaxK) - left + 1;
        }
    }

    return result;
} 

⚠️Common Pitfalls:

  • Not properly resetting the sliding window when encountering values outside the valid range.

  • Forgetting to track the last occurrences of minK and maxK.

  • Misunderstanding the relationship between subarrays and their valid bounds.

📊Time and Space Complexity:

ApproachTime Complexity    Space Complexity
Brute Force      O(n²)      O(n)
HashMap      O(n²)      O(n)
Optimized Sliding Window      O(n)      O(n)

🌍Real-World Applications:

  • Range-based queries: In applications where you need to check conditions within a specific range (e.g., in a list of user actions).

  • Data Validation: Checking whether all required conditions (min and max values) are met in a sequence of data.

  • Sliding Window Problems: Common in areas like text processing, searching for patterns, or analyzing time-series data.


I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)

Comments

Post a Comment

Popular posts from this blog

Divisible Drama — Who’s In, Who’s Out?

 Divisible Drama — Who’s In, Who’s Out? Problem Statement You’re given two positive integers n and m . num1 = sum of all numbers from 1 to n not divisible by m num2 = sum of all numbers from 1 to n divisible by m Your mission, should you choose to accept it: Return num1 - num2 Example Input: n = 10 , m = 3 Output: 19 Breakdown: Not divisible by 3 → [ 1 , 2 , 4 , 5 , 7 , 8 , 10 ] → num1 = 37 Divisible by 3 → [ 3 , 6 , 9 ] → num2 = 18 Answer = 37 - 18 = 19 Best Data Structure for Solving the Problem This one’s a math.  Why overthink it when Gauss already gave us the formula for sum of 1 to n? Different Approaches (from Brute Force to Optimized) Approach 1: Brute Force (aka List & Sum Vibes) Loop from 1 to n , split the nums based on whether they’re divisible by m , and sum them up. class Solution { public int differenceOfSums ( int n, int m) { int num1 = 0 , num2 = 0 ; for ( int i = 1 ; i <= n; i++)...
Read more

Trailing Zeros in Factorial – How Many and Why?

Trailing Zeros – Counting Zeros in Factorial Factorial-related problems are a fundamental part of Data Structures and Algorithms (DSA). One such classic problem involves counting the number of trailing zeros in N! . In this article, we will explore different approaches to solving this problem, optimize our solution, and examine its real-world applications. Optimal Data Structure for Solving the Problem For this problem, no additional data structures are required. Since factorials grow exponentially, storing the actual factorial value is impractical. Instead, we leverage mathematical properties and division operations to efficiently determine the number of trailing zeros. This approach ensures an optimal solution in terms of both time and space complexity. Approach – From Brute Force to an Optimized Solution Brute Force Approach – Compute and Count A naive approach involves computing the factorial of N and counting the number of trailing zeros. However, this method is highly ineff...
Read more

Minimum equal sum

Minimum Equal Sum – Matching Arrays with Smart Replacements Problem Statement You are given two integer arrays nums1 and nums2 , which may contain zeros. You must replace each 0 with a strictly positive integer (≥ 1) such that the sum of both arrays becomes equal . Your goal is to minimize that common equal sum after all replacements. If there is no way to make the sums equal with any valid replacements, return -1 . Example Input: nums1 = [ 3 , 2 , 0 , 1 , 0 ] nums2 = [ 6 , 5 , 0 ] Output: 12 Explanation: Replace the two zeros in nums1 with 2 and 4 → [3,2,2,1,4] Replace the zero in nums2 with 1 → [6,5,1] Both arrays now sum to 12 . Best Data Structure for the Job This problem is mostly numerical, so there’s no need for complex data structures like trees or heaps. What you do need is: A way to count zeros and compute current sums. Simple math to determine possible ranges. Long data type to handle large sums. Different Approaches Approach 1: Brute Fo...
Read more