Jobs

Interviews

Discussions

Count Complete Subarrays in an Array #99 Most Asked

Medium

TikTok

6 views

Topics:

ArraysSliding WindowsTwo Pointers

You are given an array nums consisting of positive integers.

We call a subarray of an array complete if the following condition is satisfied:

The number of distinct elements in the subarray is equal to the number of distinct elements in the whole array.

Return the number of complete subarrays.

A subarray is a contiguous non-empty part of an array.

Example 1:

Input: nums = [1,3,1,2,2]
Output: 4
Explanation: The complete subarrays are the following: [1,3,1,2], [1,3,1,2,2], [3,1,2] and [3,1,2,2].

Example 2:

Input: nums = [5,5,5,5]
Output: 10
Explanation: The array consists only of the integer 5, so any subarray is complete. The number of subarrays that we can choose is 10.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 2000

Try coding it in LeetCode

Count Complete Subarrays in an Array #99 Most Asked

Medium

TikTok

6 views

Topics:

ArraysSliding WindowsTwo Pointers

You are given an array nums consisting of positive integers.

We call a subarray of an array complete if the following condition is satisfied:

The number of distinct elements in the subarray is equal to the number of distinct elements in the whole array.

Return the number of complete subarrays.

A subarray is a contiguous non-empty part of an array.

Example 1:

Input: nums = [1,3,1,2,2]
Output: 4
Explanation: The complete subarrays are the following: [1,3,1,2], [1,3,1,2,2], [3,1,2] and [3,1,2,2].

Example 2:

Input: nums = [5,5,5,5]
Output: 10
Explanation: The array consists only of the integer 5, so any subarray is complete. The number of subarrays that we can choose is 10.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 2000

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:

Can the input array contain duplicate numbers?
What is the range of values in the input array?
Is an empty array a valid input, and if so, what should the output be?
Could you define more precisely what constitutes a 'complete' subarray in terms of its distinct element counts?
Are we looking for overlapping or non-overlapping subarrays?

Brute Force Solution

Approach

The goal is to find all the groups of numbers within a larger collection that perfectly contain all the distinct numbers from the original collection. A brute force approach tries every possible group of numbers to see if it fits the criteria.

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

Start by considering the very first number in the collection as a potential group all by itself.
Then, extend that group by adding the next number, then the next, and so on until the last number.
For each of these groups, check if it contains all the unique numbers that appear in the original larger collection. If it does, count that group.
Now, start from the second number in the collection, and repeat the same process of extending the group one number at a time.
Continue this process, starting from each number in the collection, until you have checked all possible groups.
The total count of groups that contain all the unique numbers represents the final answer.

Code Implementation

def count_complete_subarrays_brute_force(numbers):
    array_length = len(numbers)
    total_complete_subarrays = 0

    # Find all the distinct numbers in the array
    distinct_numbers = set(numbers)
    distinct_numbers_count = len(distinct_numbers)

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

            # Check if the current subarray is complete
            subarray_distinct_count = len(set(subarray))

            # A complete subarray must contain all distinct numbers.
            if subarray_distinct_count == distinct_numbers_count:
                total_complete_subarrays += 1

    return total_complete_subarrays

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible subarrays of the input array of size n. For each starting index, the algorithm expands the subarray to the right. Therefore, there is an outer loop that iterates up to n times. Within this outer loop, there is a nested loop that iterates up to n times to form all possible subarrays starting from the current index. The check within the inner loop takes O(1) time since the unique elements are pre-calculated and stored in a hash set. Consequently, the time complexity is dominated by the nested loops, which performs roughly n * n/2 operations. Thus, the overall time complexity is O(n²).

Space Complexity

O(N) – The provided algorithm, as described, implicitly uses a set or hash map (not explicitly stated but necessary for checking distinct elements) to keep track of the unique numbers present in the current subarray. In the worst-case scenario, where all numbers in the input array are distinct, this set will grow to a size of N, where N is the length of the input array. Therefore, the auxiliary space required for this set grows linearly with the input size, resulting in O(N) space complexity. We do not account for the space used by the input array itself; instead, we are only concerned with the auxiliary space.

Optimal Solution

Approach

The most efficient way to count complete subarrays involves identifying all unique elements within the entire array first. Then, we examine all possible subarrays, checking if each one contains all the unique elements we initially identified. We avoid redundant checks by only counting a subarray as complete once we've confirmed it satisfies the condition.

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

First, find out how many different numbers there are in the entire list. Keep a note of these numbers.
Next, look at every possible small section of the list. Start with sections of one number, then two, then three, and so on.
For each section, check if it contains all the different numbers you found in the first step. If it does, it's a 'complete' section.
Keep a count of all the 'complete' sections you find.
The final count is the number of 'complete' subarrays in the list.

Code Implementation

def count_complete_subarrays(nums):
    unique_elements = set(nums)
    number_of_unique_elements = len(unique_elements)
    subarray_count = 0

    for i in range(len(nums)):
        for j in range(i, len(nums)):
            subarray = nums[i:j+1]
            # Count the number of unique elements in current subarray
            unique_elements_in_subarray = set(subarray)

            # Check if all unique elements are present.
            if len(unique_elements_in_subarray) == number_of_unique_elements:

                subarray_count += 1

    return subarray_count

Big(O) Analysis

Time Complexity

O(n³) – First, finding the unique elements in the entire array takes O(n) time, where n is the size of the input array. Then, generating all possible subarrays involves nested loops, resulting in O(n²) subarrays. For each subarray, checking if it contains all unique elements requires iterating through the subarray (at most n elements) and comparing against the set of unique elements (at most n elements), leading to O(n) time. Thus, the overall time complexity is O(n) + O(n² * n) = O(n³) since we loop through all possible subarrays, and then for each subarray, check if it contains all unique elements.

Space Complexity

O(N) – The algorithm first identifies unique elements in the entire array, storing them (Step 1). In the worst-case scenario, all elements in the input array are unique, leading to storing N unique numbers. This would involve using a hash set or similar data structure to store these unique values, which grows linearly with the number of elements. Therefore, the auxiliary space complexity is O(N), where N is the number of elements in the input array.

Edge Cases

Case	How to Handle
Empty array as input	Return 0, as there are no subarrays in an empty array.
Array with a single element	If that single element is the only distinct element return 1; otherwise return 0.
Array with all identical elements	If the single distinct element is present, every subarray is complete; otherwise 0.
Array with a very large number of elements	The solution should scale linearly with the size of the input array; optimize to avoid redundant computations.
Array contains extreme boundary values (Integer.MAX_VALUE, Integer.MIN_VALUE)	The number of distinct elements calculation should handle extreme values without overflow or unexpected behavior.
No complete subarrays exist	The algorithm should correctly identify and return 0 in cases where no subarray contains all distinct elements.
Array contains negative numbers and/or zeros	The distinct element counting should handle these cases without issues (e.g., using a hash map).
Potential for integer overflow in calculations involving array size	Use appropriate data types (long) when calculating lengths or counts to avoid integer overflow.

Empty array as input

How to Handle:

Return 0, as there are no subarrays in an empty array.

Array with a single element

How to Handle:

If that single element is the only distinct element return 1; otherwise return 0.

Array with all identical elements

How to Handle:

If the single distinct element is present, every subarray is complete; otherwise 0.

Array with a very large number of elements

How to Handle:

The solution should scale linearly with the size of the input array; optimize to avoid redundant computations.

Array contains extreme boundary values (Integer.MAX_VALUE, Integer.MIN_VALUE)

How to Handle:

The number of distinct elements calculation should handle extreme values without overflow or unexpected behavior.

No complete subarrays exist

How to Handle:

The algorithm should correctly identify and return 0 in cases where no subarray contains all distinct elements.

Array contains negative numbers and/or zeros

How to Handle:

The distinct element counting should handle these cases without issues (e.g., using a hash map).

Potential for integer overflow in calculations involving array size

How to Handle:

Use appropriate data types (long) when calculating lengths or counts to avoid integer overflow.

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:

Can the input array contain duplicate numbers?
What is the range of values in the input array?
Is an empty array a valid input, and if so, what should the output be?
Could you define more precisely what constitutes a 'complete' subarray in terms of its distinct element counts?
Are we looking for overlapping or non-overlapping subarrays?

Brute Force Solution

Approach

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

Start by considering the very first number in the collection as a potential group all by itself.
Then, extend that group by adding the next number, then the next, and so on until the last number.
For each of these groups, check if it contains all the unique numbers that appear in the original larger collection. If it does, count that group.
Now, start from the second number in the collection, and repeat the same process of extending the group one number at a time.
Continue this process, starting from each number in the collection, until you have checked all possible groups.
The total count of groups that contain all the unique numbers represents the final answer.

Code Implementation

def count_complete_subarrays_brute_force(numbers):
    array_length = len(numbers)
    total_complete_subarrays = 0

    # Find all the distinct numbers in the array
    distinct_numbers = set(numbers)
    distinct_numbers_count = len(distinct_numbers)

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

            # Check if the current subarray is complete
            subarray_distinct_count = len(set(subarray))

            # A complete subarray must contain all distinct numbers.
            if subarray_distinct_count == distinct_numbers_count:
                total_complete_subarrays += 1

    return total_complete_subarrays

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, find out how many different numbers there are in the entire list. Keep a note of these numbers.
Next, look at every possible small section of the list. Start with sections of one number, then two, then three, and so on.
For each section, check if it contains all the different numbers you found in the first step. If it does, it's a 'complete' section.
Keep a count of all the 'complete' sections you find.
The final count is the number of 'complete' subarrays in the list.

Code Implementation

def count_complete_subarrays(nums):
    unique_elements = set(nums)
    number_of_unique_elements = len(unique_elements)
    subarray_count = 0

    for i in range(len(nums)):
        for j in range(i, len(nums)):
            subarray = nums[i:j+1]
            # Count the number of unique elements in current subarray
            unique_elements_in_subarray = set(subarray)

            # Check if all unique elements are present.
            if len(unique_elements_in_subarray) == number_of_unique_elements:

                subarray_count += 1

    return subarray_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array as input	Return 0, as there are no subarrays in an empty array.
Array with a single element	If that single element is the only distinct element return 1; otherwise return 0.
Array with all identical elements	If the single distinct element is present, every subarray is complete; otherwise 0.
Array with a very large number of elements	The solution should scale linearly with the size of the input array; optimize to avoid redundant computations.
Array contains extreme boundary values (Integer.MAX_VALUE, Integer.MIN_VALUE)	The number of distinct elements calculation should handle extreme values without overflow or unexpected behavior.
No complete subarrays exist	The algorithm should correctly identify and return 0 in cases where no subarray contains all distinct elements.
Array contains negative numbers and/or zeros	The distinct element counting should handle these cases without issues (e.g., using a hash map).
Potential for integer overflow in calculations involving array size	Use appropriate data types (long) when calculating lengths or counts to avoid integer overflow.

Empty array as input

How to Handle:

Return 0, as there are no subarrays in an empty array.

Array with a single element

How to Handle:

If that single element is the only distinct element return 1; otherwise return 0.

Array with all identical elements

How to Handle:

If the single distinct element is present, every subarray is complete; otherwise 0.

Array with a very large number of elements

How to Handle:

The solution should scale linearly with the size of the input array; optimize to avoid redundant computations.

Array contains extreme boundary values (Integer.MAX_VALUE, Integer.MIN_VALUE)

How to Handle:

The number of distinct elements calculation should handle extreme values without overflow or unexpected behavior.

No complete subarrays exist

How to Handle:

The algorithm should correctly identify and return 0 in cases where no subarray contains all distinct elements.

Array contains negative numbers and/or zeros

How to Handle:

The distinct element counting should handle these cases without issues (e.g., using a hash map).

Potential for integer overflow in calculations involving array size

How to Handle:

Use appropriate data types (long) when calculating lengths or counts to avoid integer overflow.

0/0 TikTok questions completed

0/0 completed