Jobs

Interviews

Discussions

Number of Subarrays with Bounded Maximum

Medium

Asked by:

10 views

Topics:

Arrays

Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the value of the maximum array element in that subarray is in the range [left, right].

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Example 2:

Input: nums = [2,9,2,5,6], left = 2, right = 8
Output: 7

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹
0 <= left <= right <= 10⁹

Try coding it in LeetCode

Number of Subarrays with Bounded Maximum

Medium

Asked by:

10 views

Topics:

Arrays

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Example 2:

Input: nums = [2,9,2,5,6], left = 2, right = 8
Output: 7

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹
0 <= left <= right <= 10⁹

Try coding it in LeetCode

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:

What are the possible ranges for the integers in the input array `nums`, and what are the constraints for the values of `left` and `right`?
Can the input array `nums` be empty or null? If so, what should the function return?
Are `left` and `right` guaranteed to satisfy `left <= right`?
If there are no subarrays that satisfy the condition (bounded maximum between `left` and `right`), what should the function return (0 or a specific error code)?
Does a subarray need to be contiguous? (Assuming yes, but confirming.)

Brute Force Solution

Approach

We want to find all the small groups of numbers from a larger list that meet specific criteria. The brute force method simply looks at every possible small group and checks if it fits.

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

First, consider every single number by itself. See if that one number meets the criteria.
Next, consider every pair of numbers that are next to each other. See if each pair meets the criteria.
Then, consider every group of three numbers that are next to each other. See if each group of three meets the criteria.
Continue doing this, making the groups bigger and bigger each time, until you've checked all possible groups up to the size of the entire list.
Count all the groups that meet the criteria. That count is your answer.

Code Implementation

def count_subarrays_brute_force(numbers, left_bound, right_bound):
    subarray_count = 0
    list_length = len(numbers)

    for subarray_length in range(1, list_length + 1):
        # Iterate through all possible subarray starting positions
        for start_index in range(list_length - subarray_length + 1):
            subarray_maximum = -float('inf')
            
            # Find the maximum element within the current subarray.
            for index in range(start_index, start_index + subarray_length):
                subarray_maximum = max(subarray_maximum, numbers[index])

            # Check if the maximum is within the specified bounds.
            if left_bound <= subarray_maximum <= right_bound:
                subarray_count += 1

    return subarray_count

Big(O) Analysis

Time Complexity

O(n³) – The outer loop iterates through all possible subarray lengths, from 1 to n, where n is the length of the input array. The middle loop iterates through all possible starting positions for a subarray of a given length. The inner loop iterates through the elements of the current subarray to find the maximum value, and then checks if the maximum is within the given bounds. Therefore, the time complexity is O(n * n * n) which simplifies to O(n³).

Space Complexity

O(1) – The provided brute force method checks every subarray by iterating through all possible starting and ending indices. While the algorithm implicitly considers various subarrays, it does not create any auxiliary data structures like temporary lists, sets, or hash maps to store these subarrays. Only constant extra space is used for loop counters and potentially to store the current subarray's maximum value. Therefore, the auxiliary space complexity remains constant regardless of the input array's size, N.

Optimal Solution

Approach

The best approach focuses on counting valid sections directly. We'll keep track of the ending positions of valid sections and efficiently add them together to get the total count, avoiding unnecessary re-calculations.

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

Go through the list of numbers one by one.
Keep track of the latest position where the number was too small (less than the lower bound).
Keep track of the latest position where the number was too big (greater than the upper bound).
If the current number is valid (between the bounds), the number of valid sections ending at this position is the current position minus the last position where the number was too small.
If the current number is too big, reset the 'last valid' position because it breaks all previous sections.
Add up the number of valid sections ending at each position to get the total count of valid sections.

Code Implementation

def number_of_subarrays_with_bounded_maximum(nums, left_bound, right_bound):
    last_too_small_position = -1
    last_too_large_position = -1
    current_subarray_count = 0
    total_subarray_count = 0

    for index, number in enumerate(nums):

        if number < left_bound:
            last_too_small_position = index

        if number > right_bound:
            # Reset because it breaks all previous sections
            last_too_large_position = index
            current_subarray_count = 0

        # Valid number, count subarrays ending here.
        elif left_bound <= number <= right_bound:
            current_subarray_count = index - last_too_small_position

        total_subarray_count += current_subarray_count

    return total_subarray_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n exactly once. Inside the loop, it performs a constant number of operations: comparisons to check if the current number is within bounds, updating the last_too_small and last_too_big positions, and calculating the number of valid subarrays ending at the current position. Because the work done inside the loop is constant for each element, the time complexity is directly proportional to the number of elements, n. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of integer variables: one to track the latest position where a number was too small, one to track the latest position where a number was too big, and one to accumulate the total count. These variables occupy a constant amount of space irrespective of the input array's size, N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty array input	Return 0 immediately as there are no subarrays.
Array with one element	Check if the single element is within the bounds (left <= element <= right) and return 1 or 0 accordingly.
All elements in the array are less than the left bound	Return 0 as no subarray will satisfy the condition.
All elements in the array are greater than the right bound	Return 0 as no subarray will satisfy the condition.
All elements in the array are within the bounds (left <= element <= right)	Return n * (n + 1) / 2, where n is the length of the array, because all subarrays are valid.
Array contains negative numbers, zeros and positive numbers	The solution should handle negative and zero values correctly as it only checks if an element is within the given bounds.
Large array size causing potential integer overflow	Use long data type for calculations involving the number of subarrays to avoid potential overflow issues.
Left bound equals Right bound	The solution should correctly identify subarrays where the maximum value equals the bound value.

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:

What are the possible ranges for the integers in the input array `nums`, and what are the constraints for the values of `left` and `right`?
Can the input array `nums` be empty or null? If so, what should the function return?
Are `left` and `right` guaranteed to satisfy `left <= right`?
If there are no subarrays that satisfy the condition (bounded maximum between `left` and `right`), what should the function return (0 or a specific error code)?
Does a subarray need to be contiguous? (Assuming yes, but confirming.)

Brute Force Solution

Approach

We want to find all the small groups of numbers from a larger list that meet specific criteria. The brute force method simply looks at every possible small group and checks if it fits.

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

First, consider every single number by itself. See if that one number meets the criteria.
Next, consider every pair of numbers that are next to each other. See if each pair meets the criteria.
Then, consider every group of three numbers that are next to each other. See if each group of three meets the criteria.
Continue doing this, making the groups bigger and bigger each time, until you've checked all possible groups up to the size of the entire list.
Count all the groups that meet the criteria. That count is your answer.

Code Implementation

def count_subarrays_brute_force(numbers, left_bound, right_bound):
    subarray_count = 0
    list_length = len(numbers)

    for subarray_length in range(1, list_length + 1):
        # Iterate through all possible subarray starting positions
        for start_index in range(list_length - subarray_length + 1):
            subarray_maximum = -float('inf')
            
            # Find the maximum element within the current subarray.
            for index in range(start_index, start_index + subarray_length):
                subarray_maximum = max(subarray_maximum, numbers[index])

            # Check if the maximum is within the specified bounds.
            if left_bound <= subarray_maximum <= right_bound:
                subarray_count += 1

    return subarray_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Go through the list of numbers one by one.
Keep track of the latest position where the number was too small (less than the lower bound).
Keep track of the latest position where the number was too big (greater than the upper bound).
If the current number is valid (between the bounds), the number of valid sections ending at this position is the current position minus the last position where the number was too small.
If the current number is too big, reset the 'last valid' position because it breaks all previous sections.
Add up the number of valid sections ending at each position to get the total count of valid sections.

Code Implementation

def number_of_subarrays_with_bounded_maximum(nums, left_bound, right_bound):
    last_too_small_position = -1
    last_too_large_position = -1
    current_subarray_count = 0
    total_subarray_count = 0

    for index, number in enumerate(nums):

        if number < left_bound:
            last_too_small_position = index

        if number > right_bound:
            # Reset because it breaks all previous sections
            last_too_large_position = index
            current_subarray_count = 0

        # Valid number, count subarrays ending here.
        elif left_bound <= number <= right_bound:
            current_subarray_count = index - last_too_small_position

        total_subarray_count += current_subarray_count

    return total_subarray_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array input	Return 0 immediately as there are no subarrays.
Array with one element	Check if the single element is within the bounds (left <= element <= right) and return 1 or 0 accordingly.
All elements in the array are less than the left bound	Return 0 as no subarray will satisfy the condition.
All elements in the array are greater than the right bound	Return 0 as no subarray will satisfy the condition.
All elements in the array are within the bounds (left <= element <= right)	Return n * (n + 1) / 2, where n is the length of the array, because all subarrays are valid.
Array contains negative numbers, zeros and positive numbers	The solution should handle negative and zero values correctly as it only checks if an element is within the given bounds.
Large array size causing potential integer overflow	Use long data type for calculations involving the number of subarrays to avoid potential overflow issues.
Left bound equals Right bound	The solution should correctly identify subarrays where the maximum value equals the bound value.