Jobs

Interviews

Discussions

Count Subarrays of Length Three With a Condition

Easy

Asked by:

8 views

Topics:

Arrays

Given an integer array nums, return the number of subarrays of length 3 such that the sum of the first and third numbers equals exactly half of the second number.

Example 1:

Input: nums = [1,2,1,4,1]

Output: 1

Explanation:

Only the subarray [1,4,1] contains exactly 3 elements where the sum of the first and third numbers equals half the middle number.

Example 2:

Input: nums = [1,1,1]

Output: 0

Explanation:

[1,1,1] is the only subarray of length 3. However, its first and third numbers do not add to half the middle number.

Constraints:

3 <= nums.length <= 100
-100 <= nums[i] <= 100

Count Subarrays of Length Three With a Condition

Easy

Asked by:

8 views

Topics:

Arrays

Given an integer array nums, return the number of subarrays of length 3 such that the sum of the first and third numbers equals exactly half of the second number.

Example 1:

Input: nums = [1,2,1,4,1]

Output: 1

Explanation:

Only the subarray [1,4,1] contains exactly 3 elements where the sum of the first and third numbers equals half the middle number.

Example 2:

Input: nums = [1,1,1]

Output: 0

Explanation:

[1,1,1] is the only subarray of length 3. However, its first and third numbers do not add to half the middle number.

Constraints:

3 <= nums.length <= 100
-100 <= nums[i] <= 100

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 constraints on the values within the `nums` array? Can they be negative, zero, or extremely large?
What are the constraints on `minRange` and `maxRange`? Can `minRange` be greater than `maxRange`?
If no subarrays satisfy the condition, what value should I return?
Can the input array `nums` be empty or have fewer than three elements?
Are the `minRange` and `maxRange` values inclusive or exclusive of the difference between the max and min values in the subarray?

Brute Force Solution

Approach

The brute force way to solve this problem is to look at every possible group of three consecutive numbers in the list. For each of these groups, we'll check if it meets the required condition.

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

Start by considering the first three numbers in the list as a group.
Check if this group of three numbers satisfies the condition we're looking for.
If the condition is met, increase a counter to track the number of valid groups.
Move to the next group of three numbers by shifting one position to the right.
Repeat the process of checking the condition and increasing the counter for each new group of three until you reach the end of the list, so there are no more consecutive groups of three numbers to check.
The final value of the counter will represent the total number of groups of three that satisfy the condition.

Code Implementation

def count_subarrays_length_three(numbers, condition):
    number_of_valid_groups = 0
    list_length = len(numbers)

    # Iterate up to the point where a group of 3 can still be formed
    for starting_index in range(list_length - 2):

        # Define the sublist based on the starting index
        sub_list = numbers[starting_index:starting_index + 3]

        # Check if the condition is met by current sublist
        if condition(sub_list):
            number_of_valid_groups += 1

    return number_of_valid_groups

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array using a sliding window of size three. For an array of size n, we examine n-2 subarrays of length three. Inside the loop, a constant amount of work is done to check if the current subarray satisfies the condition. Therefore, the time complexity is directly proportional to the size of the input array, making it O(n).

Space Complexity

O(1) – The provided solution iterates through the array, examining groups of three consecutive numbers. It utilizes a counter to track the number of valid groups found. This counter is a single variable that uses a constant amount of extra space regardless of the input array's size, N. Therefore, the space complexity is constant.

Optimal Solution

Approach

To efficiently count the valid subarrays, we avoid recomputing sums. We slide a window of size three across the numbers, updating our sum as we go and checking if the condition holds true. This avoids re-calculation of the sums for each possible subarray.

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

Consider a group of three consecutive numbers.
Calculate the value we care about for these three numbers. (e.g., their sum or average, as defined by the problem).
Check if that value meets the condition we need to satisfy (e.g., is it greater than a certain number?).
If the condition is satisfied, increase our count.
Now, instead of starting over, move the group by one number. So, we remove the first number in the group and add the next number in the sequence to the end of the group.
Update the value we care about by simply subtracting the value of the number we removed and adding the value of the number we added. This avoids recalculating the entire sum.
Repeat the check on whether the updated value satisfies the condition. If it does, increase our count.
Continue sliding the group of three numbers and updating the value until we reach the end of the number sequence.

Code Implementation

def count_subarrays(numbers, threshold):    number_of_elements = len(numbers)
    if number_of_elements < 3:
        return 0

    current_sum = sum(numbers[:3])
    average_threshold_multiplier = 3 * threshold
    valid_subarray_count = 0

    # Check the first subarray
    if current_sum > average_threshold_multiplier:
        valid_subarray_count += 1

    for index in range(3, number_of_elements):
        #Slide window; subtract element leaving, add element entering
        current_sum -= numbers[index - 3]
        current_sum += numbers[index]

        #Check if the current subarray is valid.
        if current_sum > average_threshold_multiplier:
            valid_subarray_count += 1

    return valid_subarray_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n using a sliding window of fixed size 3. Inside the loop, only constant-time operations are performed: calculating the initial sum for the first window, updating the sum by subtracting one element and adding another, and checking the condition. Thus, the overall time complexity is directly proportional to the number of iterations, which is n, making it O(n).

Space Complexity

O(1) – The algorithm uses a sliding window approach with a fixed window size of three. It only requires storing a few variables to maintain the current sum/average and the count of valid subarrays. The space used by these variables remains constant regardless of the input array's size (N). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, as no subarrays of length three can be formed.
Input array with length less than 3	Return 0, as a subarray of length three cannot be formed.
minRange greater than maxRange	Return 0, as the range is invalid and no subarray can satisfy the condition.
Large input array exceeding available memory	The solution must be designed to handle large arrays efficiently, potentially using techniques like sliding window to avoid excessive memory usage.
Input array contains very large or very small integers leading to potential overflow	Use long data type to handle potential integer overflow during max-min calculation.
All elements in the array are the same	The difference between max and min will be 0, so check if 0 is within the range [minRange, maxRange].
minRange and maxRange are both zero	Only subarrays where all elements are the same should be counted.
Input array contains negative numbers	The algorithm should correctly handle negative numbers when calculating max and min within the subarray.

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 constraints on the values within the `nums` array? Can they be negative, zero, or extremely large?
What are the constraints on `minRange` and `maxRange`? Can `minRange` be greater than `maxRange`?
If no subarrays satisfy the condition, what value should I return?
Can the input array `nums` be empty or have fewer than three elements?
Are the `minRange` and `maxRange` values inclusive or exclusive of the difference between the max and min values in the subarray?

Brute Force Solution

Approach

The brute force way to solve this problem is to look at every possible group of three consecutive numbers in the list. For each of these groups, we'll check if it meets the required condition.

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

Start by considering the first three numbers in the list as a group.
Check if this group of three numbers satisfies the condition we're looking for.
If the condition is met, increase a counter to track the number of valid groups.
Move to the next group of three numbers by shifting one position to the right.
Repeat the process of checking the condition and increasing the counter for each new group of three until you reach the end of the list, so there are no more consecutive groups of three numbers to check.
The final value of the counter will represent the total number of groups of three that satisfy the condition.

Code Implementation

def count_subarrays_length_three(numbers, condition):
    number_of_valid_groups = 0
    list_length = len(numbers)

    # Iterate up to the point where a group of 3 can still be formed
    for starting_index in range(list_length - 2):

        # Define the sublist based on the starting index
        sub_list = numbers[starting_index:starting_index + 3]

        # Check if the condition is met by current sublist
        if condition(sub_list):
            number_of_valid_groups += 1

    return number_of_valid_groups

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Consider a group of three consecutive numbers.
Calculate the value we care about for these three numbers. (e.g., their sum or average, as defined by the problem).
Check if that value meets the condition we need to satisfy (e.g., is it greater than a certain number?).
If the condition is satisfied, increase our count.
Now, instead of starting over, move the group by one number. So, we remove the first number in the group and add the next number in the sequence to the end of the group.
Update the value we care about by simply subtracting the value of the number we removed and adding the value of the number we added. This avoids recalculating the entire sum.
Repeat the check on whether the updated value satisfies the condition. If it does, increase our count.
Continue sliding the group of three numbers and updating the value until we reach the end of the number sequence.

Code Implementation

def count_subarrays(numbers, threshold):    number_of_elements = len(numbers)
    if number_of_elements < 3:
        return 0

    current_sum = sum(numbers[:3])
    average_threshold_multiplier = 3 * threshold
    valid_subarray_count = 0

    # Check the first subarray
    if current_sum > average_threshold_multiplier:
        valid_subarray_count += 1

    for index in range(3, number_of_elements):
        #Slide window; subtract element leaving, add element entering
        current_sum -= numbers[index - 3]
        current_sum += numbers[index]

        #Check if the current subarray is valid.
        if current_sum > average_threshold_multiplier:
            valid_subarray_count += 1

    return valid_subarray_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, as no subarrays of length three can be formed.
Input array with length less than 3	Return 0, as a subarray of length three cannot be formed.
minRange greater than maxRange	Return 0, as the range is invalid and no subarray can satisfy the condition.
Large input array exceeding available memory	The solution must be designed to handle large arrays efficiently, potentially using techniques like sliding window to avoid excessive memory usage.
Input array contains very large or very small integers leading to potential overflow	Use long data type to handle potential integer overflow during max-min calculation.
All elements in the array are the same	The difference between max and min will be 0, so check if 0 is within the range [minRange, maxRange].
minRange and maxRange are both zero	Only subarrays where all elements are the same should be counted.
Input array contains negative numbers	The algorithm should correctly handle negative numbers when calculating max and min within the subarray.