Jobs

Interviews

Discussions

Most Frequent Even Element

Easy

Asked by:

40 views

Topics:

Arrays

Given an integer array nums, return the most frequent even element.

If there is a tie, return the smallest one. If there is no such element, return -1.

Example 1:

Input: nums = [0,1,2,2,4,4,1]
Output: 2
Explanation:
The even elements are 0, 2, and 4. Of these, 2 and 4 appear the most.
We return the smallest one, which is 2.

Example 2:

Input: nums = [4,4,4,9,2,4]
Output: 4
Explanation: 4 is the even element appears the most.

Example 3:

Input: nums = [29,47,21,41,13,37,25,7]
Output: -1
Explanation: There is no even element.

Constraints:

1 <= nums.length <= 2000
0 <= nums[i] <= 10⁵

Try coding it in LeetCode

Most Frequent Even Element

Easy

Asked by:

40 views

Topics:

Arrays

Given an integer array nums, return the most frequent even element.

If there is a tie, return the smallest one. If there is no such element, return -1.

Example 1:

Input: nums = [0,1,2,2,4,4,1]
Output: 2
Explanation:
The even elements are 0, 2, and 4. Of these, 2 and 4 appear the most.
We return the smallest one, which is 2.

Example 2:

Input: nums = [4,4,4,9,2,4]
Output: 4
Explanation: 4 is the even element appears the most.

Example 3:

Input: nums = [29,47,21,41,13,37,25,7]
Output: -1
Explanation: There is no even element.

Constraints:

1 <= nums.length <= 2000
0 <= nums[i] <= 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 should I return if the input array is null, empty, or contains no even numbers?
What is the range of values within the input array? Is there a maximum possible value?
If multiple even numbers have the same highest frequency, which one should I return?
Can the input array contain duplicate even numbers, and if so, should they be counted towards the frequency?
Is the input array guaranteed to contain only integers?

Brute Force Solution

Approach

To find the most frequent even number, we can simply check each number individually. We will keep track of the even number we have seen the most so far and compare it to the rest of the even numbers.

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

First, make a note of all the even numbers we have.
Then, for each even number in the list, count how many times it appears.
Keep track of the even number that appears most often.
If we find another even number that appears even more often, update our most frequent even number.
In the end, the even number that we kept track of is the answer.

Code Implementation

def most_frequent_even(numbers):
    even_numbers = []
    for number in numbers:
        if number % 2 == 0:
            even_numbers.append(number)

    most_frequent_number = -1
    highest_frequency = 0

    # Check each even number to see frequency.
    for even_number in even_numbers:
        frequency = 0
        for number in even_numbers:
            if number == even_number:
                frequency += 1

        # Need to update if frequency is higher.
        if frequency > highest_frequency:

            most_frequent_number = even_number
            highest_frequency = frequency

        # In case of tie, return the smallest.
        elif frequency == highest_frequency and even_number < most_frequent_number:

            most_frequent_number = even_number

    return most_frequent_number

Big(O) Analysis

Time Complexity

O(n²) – The provided solution iterates through the input array of size n to identify even numbers. For each even number encountered, it then iterates through the entire array again to count its occurrences. This nested iteration means that for each of the (potentially n) even numbers, a comparison is made with all n elements of the array. Thus, the number of operations is proportional to n * n, resulting in a time complexity of O(n²).

Space Complexity

O(N) – The plain English explanation suggests keeping track of all the even numbers encountered. In the worst-case scenario, all N numbers in the input array could be even. To count the frequency of each even number, we implicitly need to store these even numbers, potentially in a hash map or similar data structure. This data structure will store each unique even number and its count, leading to a space complexity proportional to the number of even numbers, which in the worst case is N. Therefore, the auxiliary space required is O(N).

Optimal Solution

Approach

To efficiently find the most frequent even number, we need a way to quickly count occurrences and keep track of the number seen the most. We can achieve this by using a system that helps us count each even number and then easily find the one with the highest count.

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

First, examine each number individually to determine if it is an even number.
If the number is even, increase its count in our system for tracking frequency.
As you count, keep track of which even number has appeared most often so far, and what its count is.
If you find a new even number that occurs more often than the current most frequent one, update your record to reflect this new champion.
If you finish going through all the numbers and haven't found any even numbers, report that there aren't any.
In the end, report the even number with the highest frequency count.

Code Implementation

def mostFrequentEven(numbers):
    even_number_counts = {}
    most_frequent_even = -1
    highest_frequency = 0

    for number in numbers:
        # We only care about even numbers.
        if number % 2 == 0:

            if number in even_number_counts:
                even_number_counts[number] += 1
            else:
                even_number_counts[number] = 1

            # Check if current even number
            # is more frequent than previous.
            if even_number_counts[number] > highest_frequency:
                highest_frequency = even_number_counts[number]
                most_frequent_even = number
            elif even_number_counts[number] == highest_frequency:
                # If frequencies are the same,
                # return the smaller even number.
                most_frequent_even = min(most_frequent_even, number)

    return most_frequent_even

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n once. Inside the loop, a constant-time check is performed to determine if a number is even and update its count in a hash map (or similar data structure). Maintaining the most frequent even number seen so far also takes constant time per iteration. Thus, the runtime is dominated by the single pass through the array, resulting in O(n) time complexity.

Space Complexity

O(N) – The solution described uses a system to track the frequency of even numbers. This system most likely uses a hash map (or a similar data structure like a dictionary or an array acting as a hash map) where even numbers are keys and their counts are values. In the worst-case scenario, where all N numbers are even and distinct, the hash map will store N key-value pairs. Therefore, the auxiliary space required grows linearly with the input size N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input array	Return -1 if the input array is empty, as there are no even elements.
Array contains only odd numbers	Return -1 since there are no even elements to consider.
Array contains only one even number	Return that single even number, as it's the most frequent.
All even numbers in the array appear only once	Return the smallest even number among those with frequency one.
Integer overflow when counting frequency	Use a data type that can accommodate large counts, or check for overflows.
Array contains negative even numbers	Handle negative even numbers correctly by using a hash map that supports negative keys.
Large input array exceeding memory constraints	Consider using a streaming algorithm or external storage if the entire array cannot fit in memory.
Array with maximum integer values as even elements	The solution should handle maximum integer values without causing an integer overflow when comparing or updating frequency counts.

Empty input array

How to Handle:

Return -1 if the input array is empty, as there are no even elements.

Array contains only odd numbers

How to Handle:

Return -1 since there are no even elements to consider.

Array contains only one even number

How to Handle:

Return that single even number, as it's the most frequent.

All even numbers in the array appear only once

How to Handle:

Return the smallest even number among those with frequency one.

Integer overflow when counting frequency

How to Handle:

Use a data type that can accommodate large counts, or check for overflows.

Array contains negative even numbers

How to Handle:

Handle negative even numbers correctly by using a hash map that supports negative keys.

Large input array exceeding memory constraints

How to Handle:

Consider using a streaming algorithm or external storage if the entire array cannot fit in memory.

Array with maximum integer values as even elements

How to Handle:

The solution should handle maximum integer values without causing an integer overflow when comparing or updating frequency counts.

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 should I return if the input array is null, empty, or contains no even numbers?
What is the range of values within the input array? Is there a maximum possible value?
If multiple even numbers have the same highest frequency, which one should I return?
Can the input array contain duplicate even numbers, and if so, should they be counted towards the frequency?
Is the input array guaranteed to contain only integers?

Brute Force Solution

Approach

To find the most frequent even number, we can simply check each number individually. We will keep track of the even number we have seen the most so far and compare it to the rest of the even numbers.

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

First, make a note of all the even numbers we have.
Then, for each even number in the list, count how many times it appears.
Keep track of the even number that appears most often.
If we find another even number that appears even more often, update our most frequent even number.
In the end, the even number that we kept track of is the answer.

Code Implementation

def most_frequent_even(numbers):
    even_numbers = []
    for number in numbers:
        if number % 2 == 0:
            even_numbers.append(number)

    most_frequent_number = -1
    highest_frequency = 0

    # Check each even number to see frequency.
    for even_number in even_numbers:
        frequency = 0
        for number in even_numbers:
            if number == even_number:
                frequency += 1

        # Need to update if frequency is higher.
        if frequency > highest_frequency:

            most_frequent_number = even_number
            highest_frequency = frequency

        # In case of tie, return the smallest.
        elif frequency == highest_frequency and even_number < most_frequent_number:

            most_frequent_number = even_number

    return most_frequent_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, examine each number individually to determine if it is an even number.
If the number is even, increase its count in our system for tracking frequency.
As you count, keep track of which even number has appeared most often so far, and what its count is.
If you find a new even number that occurs more often than the current most frequent one, update your record to reflect this new champion.
If you finish going through all the numbers and haven't found any even numbers, report that there aren't any.
In the end, report the even number with the highest frequency count.

Code Implementation

def mostFrequentEven(numbers):
    even_number_counts = {}
    most_frequent_even = -1
    highest_frequency = 0

    for number in numbers:
        # We only care about even numbers.
        if number % 2 == 0:

            if number in even_number_counts:
                even_number_counts[number] += 1
            else:
                even_number_counts[number] = 1

            # Check if current even number
            # is more frequent than previous.
            if even_number_counts[number] > highest_frequency:
                highest_frequency = even_number_counts[number]
                most_frequent_even = number
            elif even_number_counts[number] == highest_frequency:
                # If frequencies are the same,
                # return the smaller even number.
                most_frequent_even = min(most_frequent_even, number)

    return most_frequent_even

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return -1 if the input array is empty, as there are no even elements.
Array contains only odd numbers	Return -1 since there are no even elements to consider.
Array contains only one even number	Return that single even number, as it's the most frequent.
All even numbers in the array appear only once	Return the smallest even number among those with frequency one.
Integer overflow when counting frequency	Use a data type that can accommodate large counts, or check for overflows.
Array contains negative even numbers	Handle negative even numbers correctly by using a hash map that supports negative keys.
Large input array exceeding memory constraints	Consider using a streaming algorithm or external storage if the entire array cannot fit in memory.
Array with maximum integer values as even elements	The solution should handle maximum integer values without causing an integer overflow when comparing or updating frequency counts.

Empty input array

How to Handle:

Return -1 if the input array is empty, as there are no even elements.

Array contains only odd numbers

How to Handle:

Return -1 since there are no even elements to consider.

Array contains only one even number

How to Handle:

Return that single even number, as it's the most frequent.

All even numbers in the array appear only once

How to Handle:

Return the smallest even number among those with frequency one.

Integer overflow when counting frequency

How to Handle:

Use a data type that can accommodate large counts, or check for overflows.

Array contains negative even numbers

How to Handle:

Handle negative even numbers correctly by using a hash map that supports negative keys.

Large input array exceeding memory constraints

How to Handle:

Consider using a streaming algorithm or external storage if the entire array cannot fit in memory.

Array with maximum integer values as even elements

How to Handle:

The solution should handle maximum integer values without causing an integer overflow when comparing or updating frequency counts.