Taro Logo

Count Subarrays With Fixed Bounds

Hard
Morgan Stanley logo
Morgan Stanley
1 view
Topics:
ArraysTwo PointersSliding Windows

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 <= 105
  • 1 <= nums[i], minK, maxK <= 106

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the possible ranges for the values in the `nums` array, `minK`, and `maxK`?
  2. Could the input array `nums` be empty, or could `minK` be equal to `maxK`? If so, what should the function return?
  3. Are `minK` and `maxK` guaranteed to be present in the `nums` array? If not, what should be returned?
  4. If a subarray contains multiple occurrences of `minK` and `maxK`, should I consider all possible combinations when counting fixed-bound subarrays?
  5. Can you provide a specific example edge case that might be tricky, to help me understand the expected behavior?

Brute Force Solution

Approach

The brute force method for this problem is like exhaustively checking every possible section of numbers to see if it meets our requirements. We'll look at every possible group of numbers, one after the other, to find the ones that work. It’s like trying every combination lock until you find the right one.

Here's how the algorithm would work step-by-step:

  1. First, consider the shortest possible group: just the very first number by itself.
  2. See if that single number meets our requirements (contains the min and max values).
  3. If it doesn't, move on. If it does, count it as a valid group.
  4. Next, look at the first two numbers as a group. Check if *they* meet the requirements.
  5. Keep adding one more number to this group, checking the requirements each time, until you reach the end of the entire list of numbers.
  6. Now, shift everything one position to the right. Start with the second number alone, then the second and third, then the second, third, and fourth, and so on. Again, check the requirements for each group.
  7. Continue shifting the starting position one number at a time, always expanding the group to the end of the list, and checking the requirements for each group you form.
  8. Every time you find a group that meets the requirements, add it to your count.
  9. Once you've checked every possible group of numbers, from single numbers to the entire list, you'll have your final count of valid groups.

Code Implementation

def count_subarrays_with_fixed_bounds_brute_force(numbers, minimum_value, maximum_value):
    subarray_count = 0
    array_length = len(numbers)

    for start_index in range(array_length):
        for end_index in range(start_index, array_length):
            current_subarray = numbers[start_index : end_index + 1]

            # Check if the subarray contains both min and max
            if minimum_value in current_subarray and maximum_value in current_subarray:

                minimum_found = False
                maximum_found = False

                for number in current_subarray:
                    if number == minimum_value:
                        minimum_found = True
                    if number == maximum_value:
                        maximum_found = True

                # Only increment if both min and max are present
                if minimum_found and maximum_found:
                    subarray_count += 1

    return subarray_count

Big(O) Analysis

Time Complexity
O(n²)The described brute force algorithm iterates through all possible subarrays of the input array of size n. The outer loop determines the starting index of the subarray, running from 0 to n-1. The inner loop expands the subarray from the starting index to the end of the array. For each subarray, it checks if the min and max values are within the fixed bounds. Consequently, the algorithm examines approximately n*(n+1)/2 subarrays, making the time complexity O(n²).
Space Complexity
O(1)The brute force approach, as described, iterates through subarrays but does not create any auxiliary data structures that scale with the input size N (the number of elements in the array). It only maintains a constant number of variables, such as indices and min/max values for each subarray being considered. Therefore, the space used remains constant irrespective of the input array's size. Consequently, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The most efficient way to solve this problem is to slide a window across the sequence of numbers. We keep track of the last places where we saw the required minimum and maximum values, and use those positions to count the valid groups of numbers efficiently.

Here's how the algorithm would work step-by-step:

  1. Go through the sequence of numbers one by one.
  2. At each number, check if it is equal to the minimum value we need.
  3. Also check if the number is equal to the maximum value we need.
  4. Remember the last position where you found the minimum and maximum values.
  5. If the current group of numbers contains both the minimum and maximum values, calculate how many valid smaller groups end here using the positions that you remembered.
  6. Add the number of these groups to your total count.
  7. If a number in the sequence is outside the required range (smaller than min or bigger than max), reset the window since no group containing it can be valid.

Code Implementation

def count_subarrays_with_fixed_bounds(nums, min_value, max_value):
    number_of_subarrays = 0
    minimum_position = -1
    maximum_position = -1
    start_of_window = 0

    for i, num in enumerate(nums):
        if num < min_value or num > max_value:
            start_of_window = i + 1
            minimum_position = -1
            maximum_position = -1

        if num == min_value:
            minimum_position = i

        if num == max_value:
            maximum_position = i

        # This checks if the current window is valid.
        if minimum_position != -1 and maximum_position != -1:

            # We choose the smaller of the two positions.
            start_index = min(minimum_position, maximum_position)

            # Calculates the number of valid subarrays ending at i.
            number_of_subarrays += (start_index - start_of_window + 1)

    return number_of_subarrays

Big(O) Analysis

Time Complexity
O(n)The algorithm iterates through the input array nums of size n exactly once. Inside the loop, we perform constant-time operations: checking if the current number is equal to the minimum or maximum value, updating the last seen positions of the minimum and maximum, and calculating the number of valid subarrays. Since the number of operations within the loop is constant and the loop executes n times, the overall time complexity is directly proportional to n. Therefore, the time complexity is O(n).
Space Complexity
O(1)The algorithm uses a few variables to store the last positions of the minimum and maximum values. These variables (and the count variable) take up a constant amount of space, regardless of the input size N (the number of elements in the sequence). No other data structures that scale with the input are used. Therefore, the auxiliary space complexity is O(1).

Edge Cases

CaseHow to Handle
Empty nums arrayReturn 0, as no subarrays can be formed.
nums array with only one element, and it equals both minK and maxKReturn 1, as the single element forms a valid subarray.
nums array with only one element, and it doesn't equal both minK and maxKReturn 0, as the single element does not form a valid subarray.
minK > maxKReturn 0, as no subarray can satisfy this condition.
nums contains only minK valuesThe solution correctly counts all possible subarrays.
nums contains only maxK valuesThe solution correctly counts all possible subarrays if minK equals maxK, otherwise 0.
nums contains only values between minK and maxK (inclusive), but neither minK nor maxK appearsReturn 0, as no valid subarray can be formed since minK and maxK must be present.
Large nums array with many valid subarrays, potentially leading to integer overflowUse a 64-bit integer type (long in Java, long long in C++) to store the count to prevent overflow.