2404. Most Frequent Even Element
Problem Description
The problem requires us to find the most frequently occurring even element in an array of integers. The steps are as follows:
- Traverse through the list of integers.
- Count the frequency of each even integer.
- Determine the even integer that appears most frequently.
If there is a tie (more than one even number with the highest frequency), we should return the smaller of those numbers. If the array does not contain any even numbers, we should return -1. These specifics need to be taken into account while implementing the solution.
Intuition
To solve this problem, we need to think about how to efficiently count the occurrences of each even number and then determine which one is the most frequent or the smallest among the most frequent. The steps include:
- Filter out all the even numbers.
- Count the occurrences of each even number.
- Track the most frequent even number.
- Handle the tie-breaking condition by comparing the current number with the most frequent one found so far, updating with the smaller number if their frequencies are the same.
- Return -1 if there are no even numbers.
The Counter
from Python's collections
module is very handy for counting frequencies, and using a conditional generator expression (x for x in nums if x % 2 == 0)
allows us to filter even numbers directly within the Counter
's constructor. Then, iterating over the items in the Counter
, we can apply our logic to track the correct answer based on the frequency (v
) and the number itself (x
). We use two variables: ans
to hold the current answer (initialized to -1) and mx
to hold the maximum frequency seen so far (initialized to 0). The loop updates these variables as needed according to the problem rules.
Solution Approach
The provided solution leverages the Counter
class from Python's collections
module to count the frequency of the even numbers. Here is how the solution is implemented:
-
Filtering Even Numbers: A generator expression is used to filter out even numbers from the
nums
list:(x for x in nums if x % 2 == 0)
. This ensures that theCounter
only processes even numbers. -
Counting Frequencies: The
Counter
is populated with the filtered even numbers, resulting in a dictionary-like object that maps each even number to its count of occurrences:Counter(x for x in nums if x % 2 == 0)
. -
Iterating Through Counts: The solution iterates over the items of the
Counter
withfor x, v in cnt.items():
, wherex
is the number andv
is its count (frequency). -
Finding the Most Frequent and Smallest: The variables
ans
andmx
are maintained to keep track of the most frequent even number and its corresponding count. During iteration, if the current countv
exceeds the maximum countmx
, or if the count equalsmx
but the current numberx
is smaller thanans
, thenans
is updated tox
andmx
is updated tov
. -
Result: The value of
ans
at the end of the iteration is the desired result. If no even numbers were found,ans
remains-1
, which is the required output for this case.
The algorithm is efficient because Counters are designed to provide constant time complexity, O(1)
, for element counting, and the additional loop to find the most frequent even number runs in linear time, O(n)
, where n
is the size of the filtered list of even numbers. Thus, the overall time complexity of the algorithm is O(n)
, where n
is the length of the input list.
The pattern used here is quite common in problems related to frequency counts where tie-breaking rules apply. By carefully designing the conditionals within the iteration loop, the algorithm efficiently solves the problem without needing to sort the input or use additional data structures.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an array of integers nums
with the following elements: [3, 5, 8, 3, 10, 8, 8, 10]
.
Following the solution approach:
-
Filtering Even Numbers: Firstly, we filter out the even numbers using the expression
(x for x in nums if x % 2 == 0)
which produces a generator for the sequence[8, 10, 8, 8, 10]
. -
Counting Frequencies: We use the
Counter
from thecollections
module on the filtered sequence to get a dictionary-like object representing the frequencies:{8: 3, 10: 2}
. This indicates that the number 8 occurs three times and the number 10 occurs two times. -
Iterating Through Counts: We then iterate through this dictionary. The loop checks both the number
x
and its frequencyv
. -
Finding the Most Frequent and Smallest: To determine the most frequent and smallest even number, the variables
ans
andmx
are set initially at-1
and0
, respectively. During the iteration:- For the first item
8:3
,v
is 3, which is greater thanmx
, somx
is updated to 3, andans
is updated to 8. - Next, for
10:2
,v
is 2, which is less thanmx
. So there is no update, andans
remains 8.
- For the first item
-
Result: At the end of the iteration, the value of
ans
is 8, which is the most frequent even number in our arraynums
. If there were no even numbers,ans
would have remained-1
.
This illustrates how the provided solution approach efficiently finds the most frequent even number or the smallest such number in the case of a tie.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def mostFrequentEven(self, nums: List[int]) -> int:
5 # Create a frequency counter for even numbers only
6 even_count = Counter([x for x in nums if x % 2 == 0])
7
8 # Initialize variables for the most frequent even number and its count
9 # Set answer to -1 initially, which means there's no even number in the list
10 most_frequent_even = -1
11 highest_frequency = 0
12
13 # Iterate over the frequency counter's items
14 for number, frequency in even_count.items():
15 # If a number has a higher frequency than the current or the same frequency but smaller in value
16 if frequency > highest_frequency or (frequency == highest_frequency and number < most_frequent_even):
17 # Update the most frequent number and the highest frequency
18 most_frequent_even = number
19 highest_frequency = frequency
20
21 # Return the most frequent even number
22 return most_frequent_even
23
24# Note: The List type hint should be imported from the typing module for complete correctness,
25# which depends on the Python version. If you are using Python 3.9 or newer, List type hints
26# are built into the Python standard library. For Python 3.8 or earlier, use `from typing import List`.
27
1class Solution {
2 public int mostFrequentEven(int[] nums) {
3 // Create a HashMap to keep track of the count of even numbers
4 Map<Integer, Integer> countMap = new HashMap<>();
5
6 // Iterate over all the elements in the array
7 for (int num : nums) {
8 // Check if the current element is even
9 if (num % 2 == 0) {
10 // If it is even, increment its count in the HashMap
11 // Using merge function to handle both existing and new numbers
12 countMap.merge(num, 1, Integer::sum);
13 }
14 }
15
16 // Variable to keep track of the most frequent even number
17 int mostFrequentNum = -1;
18 // Variable to keep track of the maximum frequency
19 int maxFrequency = 0;
20
21 // Iterate over the entries in the HashMap
22 for (var entry : countMap.entrySet()) {
23 int number = entry.getKey();
24 int frequency = entry.getValue();
25 // Check if the current frequency is greater than the maxFrequency found so far
26 // or if the frequency is same as maxFrequency and number is smaller than current mostFrequentNum
27 if (maxFrequency < frequency || (maxFrequency == frequency && mostFrequentNum > number)) {
28 // Update the most frequent number and the maximum frequency
29 mostFrequentNum = number;
30 maxFrequency = frequency;
31 }
32 }
33
34 // Return either the most frequent even number or -1 if no such number was found
35 return mostFrequentNum;
36 }
37}
38
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7 int mostFrequentEven(vector<int>& nums) {
8 unordered_map<int, int> frequencyMap; // Map to store the frequency of each even number
9 for (int num : nums) { // Iterate through the array
10 if (num % 2 == 0) { // If the element is even
11 ++frequencyMap[num]; // Increment the frequency count for this number
12 }
13 }
14
15 int mostFrequent = -1; // Variable to store the most frequent even number. Initialized to -1.
16 int maxFrequency = 0; // Variable to store the maximum frequency of an even number
17
18 // Iterate through the frequency map to find the most frequent even number
19 for (auto& keyValue : frequencyMap) {
20 int number = keyValue.first; // Current number
21 int frequency = keyValue.second; // Frequency of the current number
22
23 // Update mostFrequent if the current frequency is greater than maxFrequency
24 // or if the frequency is the same but the number is smaller
25 if (maxFrequency < frequency || (maxFrequency == frequency && mostFrequent > number)) {
26 mostFrequent = number;
27 maxFrequency = frequency; // Update the max frequency
28 }
29 }
30 return mostFrequent; // Return the most frequent even number, or -1 if none exists
31 }
32};
33
1// Finds the most frequent even element in an array of numbers.
2// If multiple elements are equally frequent, returns the smallest one.
3// If there are no even numbers, returns -1.
4function mostFrequentEven(nums: number[]): number {
5 // Map to store the count of even numbers.
6 const countMap: Map<number, number> = new Map();
7
8 // Iterate over the array and count the even numbers.
9 for (const num of nums) {
10 if (num % 2 === 0) {
11 countMap.set(num, (countMap.get(num) ?? 0) + 1);
12 }
13 }
14
15 // Variable to keep track of the most frequent even number.
16 let answer: number = -1;
17 // Variable to keep track of the highest occurrence count found so far.
18 let maxCount: number = 0;
19
20 // Iterate over the countMap to find the most frequent even number.
21 for (const [number, count] of countMap) {
22 // If the count for the current number is greater than maxCount,
23 // or if the count is equal but the number is smaller than the current answer,
24 // update answer and maxCount.
25 if (maxCount < count || (maxCount === count && answer > number)) {
26 answer = number;
27 maxCount = count;
28 }
29 }
30
31 // Return the most frequent even number or -1 if there are no even numbers.
32 return answer;
33}
34
Time and Space Complexity
The given code snippet is a Python function that finds the most frequent even element in a list. To compute the time complexity and space complexity, let's analyse the given operations:
-
A
Counter
object is constructed with a generator expression:Counter(x for x in nums if x % 2 == 0)
. This step goes through alln
elements ofnums
, checking forx % 2 == 0
to consider only even numbers. Therefore, this step has a time complexity ofO(n)
. -
The
ans
andmx
variables are initialized. This is a constant time operation, so its time complexity isO(1)
. -
A
for
loop iterates over each item in theCounter
object:for x, v in cnt.items()
. This could be up ton
iterations in the worst case (if all numbers innums
are even and unique). However, since the total number of unique elements in theCounter
object is unlikely to ben
, let's assume there arek
unique even numbers after filtering. The time complexity for this loop isO(k)
. -
Inside the loop, there are a few constant time comparisons, and possibly an assignment operation. These constant time operations inside the loop do not affect the overall time complexity of
O(k)
for the loop.
Therefore, the total time complexity is the sum of all these steps, which would be O(n)
+ O(k)
. Since k
is bounded by n
, the worst-case time complexity simplifies to O(n)
.
As for space complexity:
-
The
Counter
object will hold at mostk
unique even numbers, which requiresO(k)
space. -
The
ans
andmx
variables are constant space,O(1)
.
The total space complexity is O(k)
. Since k
is bounded by n
, the worst-case space complexity is O(n)
.
In conclusion:
- Time Complexity:
O(n)
- Space Complexity:
O(n)
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!