Jobs

Interviews

Discussions

Frequency of the Most Frequent Element

Medium

Asked by:

More companies

65 views

Topics:

ArraysSliding WindowsGreedy Algorithms

The frequency of an element is the number of times it occurs in an array.

You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1.

Return the maximum possible frequency of an element after performing at most k operations.

Example 1:

Input: nums = [1,2,4], k = 5
Output: 3
Explanation: Increment the first element three times and the second element two times to make nums = [4,4,4].
4 has a frequency of 3.

Example 2:

Input: nums = [1,4,8,13], k = 5
Output: 2
Explanation: There are multiple optimal solutions:
- Increment the first element three times to make nums = [4,4,8,13]. 4 has a frequency of 2.
- Increment the second element four times to make nums = [1,8,8,13]. 8 has a frequency of 2.
- Increment the third element five times to make nums = [1,4,13,13]. 13 has a frequency of 2.

Example 3:

Input: nums = [3,9,6], k = 2
Output: 1

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
1 <= k <= 10⁵

Try coding it in LeetCode

Frequency of the Most Frequent Element

Medium

Asked by:

More companies

65 views

Topics:

ArraysSliding WindowsGreedy Algorithms

The frequency of an element is the number of times it occurs in an array.

You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1.

Return the maximum possible frequency of an element after performing at most k operations.

Example 1:

Input: nums = [1,2,4], k = 5
Output: 3
Explanation: Increment the first element three times and the second element two times to make nums = [4,4,4].
4 has a frequency of 3.

Example 2:

Input: nums = [1,4,8,13], k = 5
Output: 2
Explanation: There are multiple optimal solutions:
- Increment the first element three times to make nums = [4,4,8,13]. 4 has a frequency of 2.
- Increment the second element four times to make nums = [1,8,8,13]. 8 has a frequency of 2.
- Increment the third element five times to make nums = [1,4,13,13]. 13 has a frequency of 2.

Example 3:

Input: nums = [3,9,6], k = 2
Output: 1

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
1 <= k <= 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:

Are the elements in the input array `nums` guaranteed to be positive integers, or could they be zero or negative?
What is the maximum possible value for `k` and the maximum number of elements in the `nums` array?
If the input array `nums` is empty, what should be returned?
Can we increment an element to become equal to any other element in the array, or does the target element have to exist in the original array?
Is it possible to increment an element multiple times towards the same target value, or is each increment a distinct operation?

Brute Force Solution

Approach

The problem asks us to find the largest possible value that can be achieved by making an element in a collection equal to some other element, by repeatedly increasing that element. The brute force way to solve this is to consider every possible target value and see how much effort it takes to reach it.

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

For each distinct value present in the collection, imagine we want to transform all other values into this specific value.
For a chosen target value, calculate the total cost required to change every other value in the collection to match this target value.
The cost is simply the sum of the differences between each individual value and the target value.
Keep track of the smallest cost found so far.
After checking every distinct value as a potential target, the smallest cost we recorded will be our answer. This smallest cost represents the minimum effort needed to make all elements equal to some common value within the collection.

Code Implementation

def min_operations_to_equalize(collection_of_numbers):
    minimum_total_operations = float('inf')

    # We need to consider each unique number as a potential target value
    unique_numbers = sorted(list(set(collection_of_numbers)))

    for potential_target_value in unique_numbers:
        current_total_operations = 0
        # Calculate the cost to transform all other numbers to this target
        for number_to_transform in collection_of_numbers:
            difference = abs(number_to_transform - potential_target_value)
            current_total_operations += difference

        # Keep track of the smallest cost found so far
        minimum_total_operations = min(minimum_total_operations, current_total_operations)

    # The smallest cost represents the minimum effort needed to equalize elements
    return minimum_total_operations

Big(O) Analysis

Time Complexity

O(n*k) – Let n be the number of elements in the input collection and k be the number of distinct elements. The approach iterates through each of the k distinct elements as a potential target value. For each target, it then iterates through all n elements of the original collection to calculate the cost of transforming them to the target. This results in a complexity of O(k*n). In the worst case, if all elements are distinct, k can be up to n, leading to O(n²). However, if the number of distinct elements is significantly smaller than n, the complexity is closer to O(n).

Space Complexity

O(1) – The provided algorithm iterates through the input collection to calculate costs. It primarily uses a few scalar variables to store the current element, the target value, the current cost, and the minimum cost found so far. These variables consume a constant amount of extra memory, independent of the input size N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

This problem asks us to find the largest possible frequency of any number in a list after we are allowed to increase some numbers to match a target number. The key idea is to efficiently check how many times each number *could* become the most frequent.

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

First, sort all the numbers in the list from smallest to largest.
Imagine we pick a specific number in the sorted list and decide to make it the most frequent number. We'll try to make all the numbers to its left equal to this chosen number.
To do this, we add up the differences between the chosen number and all the numbers to its left that are smaller.
If the total amount we need to add to make those smaller numbers equal to the chosen number is less than or equal to the allowed 'budget' for additions, then it's possible for our chosen number to become the most frequent with that many occurrences.
We want to find the largest group of numbers (including the chosen number itself) that we can 'convert' to this chosen number within the budget.
Instead of checking every single number as a potential 'most frequent' target and then looking left, we can use a sliding window approach. Think of a window that expands to the right.
As the window expands, we keep track of the total 'cost' to make all numbers within the window equal to the rightmost number in the window.
If this cost exceeds our budget, we shrink the window from the left, subtracting the cost of the number that left the window.
At each step, we see if the current size of the window is larger than any successful window size we've found so far.
The largest window size we can achieve while staying within our budget is our answer.

Code Implementation

def get_max_frequency(numbers_list, allowed_operations_budget):
    numbers_list.sort()
    maximum_frequency_achieved = 0
    current_window_sum = 0
    window_start_index = 0

    # We use a sliding window to efficiently check contiguous subarrays.
    for window_end_index in range(len(numbers_list)):
        current_number_to_match = numbers_list[window_end_index]
        current_window_size = window_end_index - window_start_index + 1
        cost_to_make_equal = (current_number_to_match * current_window_size) - current_window_sum

        # If the cost exceeds budget, we must shrink the window from the left.
        while cost_to_make_equal > allowed_operations_budget and window_start_index <= window_end_index:
            number_leaving_window = numbers_list[window_start_index]
            current_window_sum -= number_leaving_window
            window_start_index += 1
            current_window_size = window_end_index - window_start_index + 1
            cost_to_make_equal = (current_number_to_match * current_window_size) - current_window_sum

        # After adjusting the window, update maximum frequency if current window is larger.
        current_window_sum += current_number_to_match
        maximum_frequency_achieved = max(maximum_frequency_achieved, current_window_size)

    return maximum_frequency_achieved

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is the initial sorting of the input array, which takes O(n log n) time. After sorting, the sliding window approach iterates through the array once. The window expands and contracts, but each element is added to and removed from the window at most once. Calculating the sum within the window takes constant time per step as we maintain a running sum. Therefore, the linear scan with the sliding window contributes O(n) time complexity, and the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(n) – The primary auxiliary space used is for sorting the input array in-place or by creating a sorted copy. If an in-place sort is used (like heapsort or some quicksort implementations), the auxiliary space is O(log n) due to the recursion stack or O(1) for iterative sorts. However, if a separate sorted array is created (like merge sort or timsort), it requires O(n) auxiliary space. The sliding window approach itself only uses a few constant variables (left pointer, right pointer, current sum, max frequency), which do not scale with input size N. Therefore, the dominant factor in space complexity comes from the sorting step, leading to an auxiliary space complexity of O(n) in the general case where a temporary sorted array might be used.

Edge Cases

Case	How to Handle
Empty input array nums	An empty array should result in a frequency of 0 as no elements exist to increment.
Input array nums with a single element	With a single element, its frequency is 1, and we can potentially increment it using k operations, but the maximum frequency remains 1 without any other elements to match.
k is 0	If k is 0, no operations can be performed, so the maximum frequency is simply the frequency of the most frequent element in the original array.
All elements in nums are identical	If all elements are identical, their initial frequency is the array length, and no operations are needed or will increase this frequency.
nums contains extremely large positive integers	The solution must handle potential integer overflow if the sum of increments or intermediate calculations exceed the maximum value for the integer type.
k is extremely large, enough to make all elements equal to the largest element	A large k allows us to equalize many elements, and the algorithm should correctly identify the largest possible group achievable.
nums contains only small positive integers, and k is large	The algorithm should efficiently identify that making all elements equal to the largest element is optimal, even if it requires many operations.
The difference between elements is very large, requiring many increments	The solution needs to be efficient enough to handle cases where large increments are necessary without timing out.

Empty input array nums

How to Handle:

An empty array should result in a frequency of 0 as no elements exist to increment.

Input array nums with a single element

How to Handle:

With a single element, its frequency is 1, and we can potentially increment it using k operations, but the maximum frequency remains 1 without any other elements to match.

k is 0

How to Handle:

If k is 0, no operations can be performed, so the maximum frequency is simply the frequency of the most frequent element in the original array.

All elements in nums are identical

How to Handle:

If all elements are identical, their initial frequency is the array length, and no operations are needed or will increase this frequency.

nums contains extremely large positive integers

How to Handle:

The solution must handle potential integer overflow if the sum of increments or intermediate calculations exceed the maximum value for the integer type.

k is extremely large, enough to make all elements equal to the largest element

How to Handle:

A large k allows us to equalize many elements, and the algorithm should correctly identify the largest possible group achievable.

nums contains only small positive integers, and k is large

How to Handle:

The algorithm should efficiently identify that making all elements equal to the largest element is optimal, even if it requires many operations.

The difference between elements is very large, requiring many increments

How to Handle:

The solution needs to be efficient enough to handle cases where large increments are necessary without timing out.

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:

Are the elements in the input array `nums` guaranteed to be positive integers, or could they be zero or negative?
What is the maximum possible value for `k` and the maximum number of elements in the `nums` array?
If the input array `nums` is empty, what should be returned?
Can we increment an element to become equal to any other element in the array, or does the target element have to exist in the original array?
Is it possible to increment an element multiple times towards the same target value, or is each increment a distinct operation?

Brute Force Solution

Approach

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

For each distinct value present in the collection, imagine we want to transform all other values into this specific value.
For a chosen target value, calculate the total cost required to change every other value in the collection to match this target value.
The cost is simply the sum of the differences between each individual value and the target value.
Keep track of the smallest cost found so far.
After checking every distinct value as a potential target, the smallest cost we recorded will be our answer. This smallest cost represents the minimum effort needed to make all elements equal to some common value within the collection.

Code Implementation

def min_operations_to_equalize(collection_of_numbers):
    minimum_total_operations = float('inf')

    # We need to consider each unique number as a potential target value
    unique_numbers = sorted(list(set(collection_of_numbers)))

    for potential_target_value in unique_numbers:
        current_total_operations = 0
        # Calculate the cost to transform all other numbers to this target
        for number_to_transform in collection_of_numbers:
            difference = abs(number_to_transform - potential_target_value)
            current_total_operations += difference

        # Keep track of the smallest cost found so far
        minimum_total_operations = min(minimum_total_operations, current_total_operations)

    # The smallest cost represents the minimum effort needed to equalize elements
    return minimum_total_operations

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, sort all the numbers in the list from smallest to largest.
Imagine we pick a specific number in the sorted list and decide to make it the most frequent number. We'll try to make all the numbers to its left equal to this chosen number.
To do this, we add up the differences between the chosen number and all the numbers to its left that are smaller.
If the total amount we need to add to make those smaller numbers equal to the chosen number is less than or equal to the allowed 'budget' for additions, then it's possible for our chosen number to become the most frequent with that many occurrences.
We want to find the largest group of numbers (including the chosen number itself) that we can 'convert' to this chosen number within the budget.
Instead of checking every single number as a potential 'most frequent' target and then looking left, we can use a sliding window approach. Think of a window that expands to the right.
As the window expands, we keep track of the total 'cost' to make all numbers within the window equal to the rightmost number in the window.
If this cost exceeds our budget, we shrink the window from the left, subtracting the cost of the number that left the window.
At each step, we see if the current size of the window is larger than any successful window size we've found so far.
The largest window size we can achieve while staying within our budget is our answer.

Code Implementation

def get_max_frequency(numbers_list, allowed_operations_budget):
    numbers_list.sort()
    maximum_frequency_achieved = 0
    current_window_sum = 0
    window_start_index = 0

    # We use a sliding window to efficiently check contiguous subarrays.
    for window_end_index in range(len(numbers_list)):
        current_number_to_match = numbers_list[window_end_index]
        current_window_size = window_end_index - window_start_index + 1
        cost_to_make_equal = (current_number_to_match * current_window_size) - current_window_sum

        # If the cost exceeds budget, we must shrink the window from the left.
        while cost_to_make_equal > allowed_operations_budget and window_start_index <= window_end_index:
            number_leaving_window = numbers_list[window_start_index]
            current_window_sum -= number_leaving_window
            window_start_index += 1
            current_window_size = window_end_index - window_start_index + 1
            cost_to_make_equal = (current_number_to_match * current_window_size) - current_window_sum

        # After adjusting the window, update maximum frequency if current window is larger.
        current_window_sum += current_number_to_match
        maximum_frequency_achieved = max(maximum_frequency_achieved, current_window_size)

    return maximum_frequency_achieved

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array nums	An empty array should result in a frequency of 0 as no elements exist to increment.
Input array nums with a single element	With a single element, its frequency is 1, and we can potentially increment it using k operations, but the maximum frequency remains 1 without any other elements to match.
k is 0	If k is 0, no operations can be performed, so the maximum frequency is simply the frequency of the most frequent element in the original array.
All elements in nums are identical	If all elements are identical, their initial frequency is the array length, and no operations are needed or will increase this frequency.
nums contains extremely large positive integers	The solution must handle potential integer overflow if the sum of increments or intermediate calculations exceed the maximum value for the integer type.
k is extremely large, enough to make all elements equal to the largest element	A large k allows us to equalize many elements, and the algorithm should correctly identify the largest possible group achievable.
nums contains only small positive integers, and k is large	The algorithm should efficiently identify that making all elements equal to the largest element is optimal, even if it requires many operations.
The difference between elements is very large, requiring many increments	The solution needs to be efficient enough to handle cases where large increments are necessary without timing out.

Empty input array nums

How to Handle:

An empty array should result in a frequency of 0 as no elements exist to increment.

Input array nums with a single element

How to Handle:

With a single element, its frequency is 1, and we can potentially increment it using k operations, but the maximum frequency remains 1 without any other elements to match.

k is 0

How to Handle:

If k is 0, no operations can be performed, so the maximum frequency is simply the frequency of the most frequent element in the original array.

All elements in nums are identical

How to Handle:

If all elements are identical, their initial frequency is the array length, and no operations are needed or will increase this frequency.

nums contains extremely large positive integers

How to Handle:

The solution must handle potential integer overflow if the sum of increments or intermediate calculations exceed the maximum value for the integer type.

k is extremely large, enough to make all elements equal to the largest element

How to Handle:

A large k allows us to equalize many elements, and the algorithm should correctly identify the largest possible group achievable.

nums contains only small positive integers, and k is large

How to Handle:

The algorithm should efficiently identify that making all elements equal to the largest element is optimal, even if it requires many operations.

The difference between elements is very large, requiring many increments

How to Handle:

The solution needs to be efficient enough to handle cases where large increments are necessary without timing out.