Jobs

Interviews

Discussions

Count Subarrays Where Max Element Appears at Least K Times

Medium

Apple

2 views

Topics:

Arrays

You are given an integer array nums and a positive integer k.

Return the number of subarrays where the maximum element of nums appears at least k times in that subarray.

A subarray is a contiguous sequence of elements within an array.

For example:

nums = [1, 3, 2, 3, 3], k = 2

Output: 6

Explanation: The subarrays that contain the element 3 at least 2 times are: [1,3,2,3], [1,3,2,3,3], [3,2,3], [3,2,3,3], [2,3,3] and [3,3].

Another example:

nums = [1, 4, 2, 1], k = 3

Output: 0

Explanation: No subarray contains the element 4 at least 3 times.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1 <= k <= 10^5

Write a function to solve this problem efficiently.

Count Subarrays Where Max Element Appears at Least K Times

Medium

Apple

2 views

Topics:

Arrays

You are given an integer array nums and a positive integer k.

Return the number of subarrays where the maximum element of nums appears at least k times in that subarray.

A subarray is a contiguous sequence of elements within an array.

For example:

nums = [1, 3, 2, 3, 3], k = 2

Output: 6

Explanation: The subarrays that contain the element 3 at least 2 times are: [1,3,2,3], [1,3,2,3,3], [3,2,3], [3,2,3,3], [2,3,3] and [3,3].

Another example:

nums = [1, 4, 2, 1], k = 3

Output: 0

Explanation: No subarray contains the element 4 at least 3 times.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1 <= k <= 10^5

Write a function to solve this problem efficiently.

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 size of the input array `nums` and the value of `k`?
Can the input array `nums` contain negative numbers, zeros, or floating-point numbers?
If no subarrays satisfy the condition, should I return 0?
In a subarray, if the maximum element appears more than `k` times, do I still count that subarray?
Could you provide an example input with its corresponding output to confirm my understanding of the problem?

Brute Force Solution

Approach

The basic idea is to look at every possible chunk of numbers within the entire sequence. For each of these chunks, we'll count how many times the biggest number in the entire sequence appears within that chunk.

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

First, pick a starting point in the sequence.
Then, consider all possible chunks that start at that point: the chunk of just the first number, the chunk of the first two numbers, the chunk of the first three numbers, and so on, until you reach the end of the sequence.
For each of these chunks, find the biggest number in the original sequence. Then count how many times that biggest number shows up in the chunk you're currently looking at.
If the biggest number appears at least the required number of times, then count that chunk as a valid subarray.
Repeat this process for every possible starting point in the sequence, moving one number at a time.
Add up all the valid subarray counts you found along the way. The total count represents the answer to the problem.

Code Implementation

def count_subarrays_where_max_element_appears_at_least_k_times(
    sequence_of_numbers, required_number_of_times
):    number_of_valid_subarrays = 0
    sequence_length = len(sequence_of_numbers)
    
    # Find the maximum element in the entire sequence
    maximum_element_in_sequence = max(sequence_of_numbers)
    
    for start_index in range(sequence_length):
        for end_index in range(start_index, sequence_length):
            current_subarray =
                sequence_of_numbers[start_index : end_index + 1]
            
            # Count occurrences of max element in the current subarray
            maximum_element_count = 0
            for element in current_subarray:
                if element == maximum_element_in_sequence:
                    maximum_element_count += 1
            
            # Check if max element appears at least k times
            if (
                maximum_element_count >= required_number_of_times
            ):
                number_of_valid_subarrays += 1

    return number_of_valid_subarrays

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates through each element of the input array of size n as a starting point for a subarray, leading to an outer loop that runs n times. For each starting point, it considers all possible subarrays that begin at that point, resulting in a nested loop that also runs up to n times. Within the inner loop, for each subarray, it counts the occurrences of the maximum element in the original array. Counting the occurrences in each subarray requires iterating through the subarray, taking O(n) time in the worst case. Thus, the total time complexity is O(n * n * n) which simplifies to O(n³).

Space Complexity

O(1) – The algorithm iterates through subarrays by picking a starting point and extending the subarray. It checks the count of the maximum element within each subarray. This process only requires a few integer variables to store indices, the count of the maximum element, and the overall result. No auxiliary data structures like lists or hash maps are used that scale with the input size N (the length of the sequence). Therefore, the space complexity is constant.

Optimal Solution

Approach

The goal is to efficiently count valid segments in a list. The key is to avoid recounting segments by reusing information about previously counted segments and focusing on segments that become valid as we move through the list.

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

First, find the largest number in the list, since that number has to appear a certain number of times.
Then, use a sliding window approach. Think of a window that moves from left to right along the list.
Keep track of how many times the largest number appears inside the current window.
If the largest number appears at least the required number of times within the window, you know that all segments starting from the left edge of the window are valid. Count all of these segments.
Move the window one step to the right. If the largest number is still frequent enough, all segments starting at the beginning of the window are valid. Otherwise, reduce the window size from the left until the largest number appears frequently enough again.
Continue this sliding and adjusting process until the window reaches the end of the list. The total count of valid segments will be your answer.

Code Implementation

def count_subarrays(number_list, min_occurrences):
    list_length = len(number_list)
    if list_length == 0:
        return 0

    maximum_number = max(number_list)
    subarray_count = 0
    window_start = 0
    max_number_count = 0

    for window_end in range(list_length):
        if number_list[window_end] == maximum_number:
            max_number_count += 1

        # Shrink window from left if necessary
        while max_number_count >= min_occurrences:

            # Add valid subarrays ending at window_end
            subarray_count += list_length - window_end

            if number_list[window_start] == maximum_number:
                max_number_count -= 1

            window_start += 1

    return subarray_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input list of size n once to find the maximum element. Subsequently, the sliding window approach processes each element in the list. Although the inner while loop might seem to suggest a nested structure, the crucial observation is that each element is added to the window and removed from the window at most once. Therefore, the total number of operations performed by both the outer for loop and the inner while loop is proportional to n, resulting in a time complexity of O(n).

Space Complexity

O(1) – The algorithm's space complexity is determined by the number of times the largest element appears within the current sliding window, which is tracked using a counter variable. The plain English explanation does not indicate the use of auxiliary data structures that scale with the input size, N (the length of the list). Therefore, it utilizes a constant amount of extra space for variables regardless of the input list's length, resulting in a space complexity of O(1).

Edge Cases

Case	How to Handle
Empty input array	Return 0 since no subarrays are possible.
k is zero or negative	If k is zero return the number of all possible subarrays; if negative treat as zero.
Array with one element	Check if k is 1 and if the element is the max (which it is) and return 1, else return 0.
Array with all identical elements	If k is less than or equal to length of the subarray (which is the same element's count), the subarray is valid; count total valid subarrays.
Array with negative numbers	The algorithm should correctly find the maximum element and its frequency regardless of negative values.
Large array and large k values potentially exceeding integer limits in counting	Use long or appropriate data type to store the count of valid subarrays and maximum element frequencies to prevent overflow.
k is greater than the length of the input array	No subarray can satisfy the condition; return 0.
Array contains Integer.MAX_VALUE or Integer.MIN_VALUE	Compare elements carefully to correctly identify the maximum even with extreme values.

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 size of the input array `nums` and the value of `k`?
Can the input array `nums` contain negative numbers, zeros, or floating-point numbers?
If no subarrays satisfy the condition, should I return 0?
In a subarray, if the maximum element appears more than `k` times, do I still count that subarray?
Could you provide an example input with its corresponding output to confirm my understanding of the problem?

Brute Force Solution

Approach

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

First, pick a starting point in the sequence.
Then, consider all possible chunks that start at that point: the chunk of just the first number, the chunk of the first two numbers, the chunk of the first three numbers, and so on, until you reach the end of the sequence.
For each of these chunks, find the biggest number in the original sequence. Then count how many times that biggest number shows up in the chunk you're currently looking at.
If the biggest number appears at least the required number of times, then count that chunk as a valid subarray.
Repeat this process for every possible starting point in the sequence, moving one number at a time.
Add up all the valid subarray counts you found along the way. The total count represents the answer to the problem.

Code Implementation

def count_subarrays_where_max_element_appears_at_least_k_times(
    sequence_of_numbers, required_number_of_times
):    number_of_valid_subarrays = 0
    sequence_length = len(sequence_of_numbers)
    
    # Find the maximum element in the entire sequence
    maximum_element_in_sequence = max(sequence_of_numbers)
    
    for start_index in range(sequence_length):
        for end_index in range(start_index, sequence_length):
            current_subarray =
                sequence_of_numbers[start_index : end_index + 1]
            
            # Count occurrences of max element in the current subarray
            maximum_element_count = 0
            for element in current_subarray:
                if element == maximum_element_in_sequence:
                    maximum_element_count += 1
            
            # Check if max element appears at least k times
            if (
                maximum_element_count >= required_number_of_times
            ):
                number_of_valid_subarrays += 1

    return number_of_valid_subarrays

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, find the largest number in the list, since that number has to appear a certain number of times.
Then, use a sliding window approach. Think of a window that moves from left to right along the list.
Keep track of how many times the largest number appears inside the current window.
If the largest number appears at least the required number of times within the window, you know that all segments starting from the left edge of the window are valid. Count all of these segments.
Move the window one step to the right. If the largest number is still frequent enough, all segments starting at the beginning of the window are valid. Otherwise, reduce the window size from the left until the largest number appears frequently enough again.
Continue this sliding and adjusting process until the window reaches the end of the list. The total count of valid segments will be your answer.

Code Implementation

def count_subarrays(number_list, min_occurrences):
    list_length = len(number_list)
    if list_length == 0:
        return 0

    maximum_number = max(number_list)
    subarray_count = 0
    window_start = 0
    max_number_count = 0

    for window_end in range(list_length):
        if number_list[window_end] == maximum_number:
            max_number_count += 1

        # Shrink window from left if necessary
        while max_number_count >= min_occurrences:

            # Add valid subarrays ending at window_end
            subarray_count += list_length - window_end

            if number_list[window_start] == maximum_number:
                max_number_count -= 1

            window_start += 1

    return subarray_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 since no subarrays are possible.
k is zero or negative	If k is zero return the number of all possible subarrays; if negative treat as zero.
Array with one element	Check if k is 1 and if the element is the max (which it is) and return 1, else return 0.
Array with all identical elements	If k is less than or equal to length of the subarray (which is the same element's count), the subarray is valid; count total valid subarrays.
Array with negative numbers	The algorithm should correctly find the maximum element and its frequency regardless of negative values.
Large array and large k values potentially exceeding integer limits in counting	Use long or appropriate data type to store the count of valid subarrays and maximum element frequencies to prevent overflow.
k is greater than the length of the input array	No subarray can satisfy the condition; return 0.
Array contains Integer.MAX_VALUE or Integer.MIN_VALUE	Compare elements carefully to correctly identify the maximum even with extreme values.