Most Frequent Even Element
EasyPrompt
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 <= 20000 <= nums[i] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a straightforward, brute-force method. It involves iterating through each element of the array and, for each even element, iterating through the entire array again to count its frequency. It keeps track of the most frequent even number found so far, handling ties by choosing the smaller value.
Algorithm
- Initialize
mostFrequentEvento -1 andmaxFrequencyto 0. - Iterate through the input array
numswith an outer loop (let's say indexi). - For each element
nums[i], check if it's an even number. - If
nums[i]is even, start an inner loop (indexj) to iterate through the entire array again to count its occurrences. - Let the count be
currentFrequency. - After the inner loop, compare
currentFrequencywithmaxFrequency:- If
currentFrequency > maxFrequency, it means we've found a new more frequent even number. UpdatemaxFrequency = currentFrequencyandmostFrequentEven = nums[i]. - If
currentFrequency == maxFrequency, we have a tie. According to the problem, we should choose the smaller element. So, updatemostFrequentEven = min(mostFrequentEven, nums[i]).
- If
- After the outer loop completes,
mostFrequentEvenwill hold the result.
Walkthrough
The core idea is to test every even number as a potential candidate for the most frequent one. We use two nested loops. The outer loop picks an element, and the inner loop counts its frequency. We maintain two variables: maxFrequency to store the highest frequency seen so far, and mostFrequentEven to store the corresponding element. When we find an element with a frequency greater than maxFrequency, we update both variables. If we find an element with a frequency equal to maxFrequency, we only update mostFrequentEven if the current element is smaller than the one we have stored, thus satisfying the tie-breaker rule.
class Solution { public int mostFrequentEven(int[] nums) { int mostFrequentEven = -1; int maxFreq = 0; // To avoid re-calculating for the same number, we can sort first, // but that would change the approach. A pure brute-force would be: for (int i = 0; i < nums.length; i++) { if (nums[i] % 2 == 0) { int currentFreq = 0; // Inner loop to count frequency of nums[i] for (int j = 0; j < nums.length; j++) { if (nums[j] == nums[i]) { currentFreq++; } } if (currentFreq > maxFreq) { maxFreq = currentFreq; mostFrequentEven = nums[i]; } else if (currentFreq == maxFreq) { // If frequencies are tied, choose the smaller element if (mostFrequentEven == -1 || nums[i] < mostFrequentEven) { mostFrequentEven = nums[i]; } } } } return mostFrequentEven; }}Complexity
Time
O(N^2), where N is the number of elements in the `nums` array. The nested loops cause the complexity to be quadratic, as for each element, we may scan the entire array again.
Space
O(1), as we only use a few variables to store the result and current state, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space, O(1).
Cons
Highly inefficient due to the nested loops.
Will likely result in a 'Time Limit Exceeded' (TLE) error for larger input arrays as specified by the constraints.
A more optimized approach involves sorting the array first. By sorting, all identical elements are grouped together, which allows us to count their frequencies in a single pass. We can then iterate through the sorted array, keeping track of the frequency of the current element and updating our answer if we find a more frequent even element.
Algorithm
- First, sort the input array
numsin non-decreasing order. This will group all identical elements together. - Initialize
ans = -1(the result),maxFreq = 0(the max frequency found). - Iterate through the sorted array using a pointer
i. - If the current element
nums[i]is odd, skip it and move to the next element. - If
nums[i]is even, find its frequency by counting how many consecutive elements are identical. Use another pointerjto find the end of the block of identical elements. - The frequency of
nums[i]iscurrentFreq = j - i. - If
currentFreq > maxFreq, we have found a new most frequent element. UpdatemaxFreq = currentFreqandans = nums[i]. - Since the array is sorted, the first time we encounter a particular maximum frequency, it will be with the smallest number. Therefore, we don't need to handle the tie-breaking case explicitly.
- Move the pointer
itojto start processing the next distinct number. - After the loop, return
ans.
Walkthrough
Sorting the array simplifies frequency counting significantly. After sorting, we can iterate through the array once. We use a pointer i to mark the beginning of a sequence of identical numbers. We then find out how long this sequence is. If the number is even, we compare its frequency with the maximum frequency found so far. Because the array is sorted, the first element we find for a given frequency will always be the smallest one, automatically handling the tie-breaking rule.
import java.util.Arrays; class Solution { public int mostFrequentEven(int[] nums) { Arrays.sort(nums); int ans = -1; int maxFreq = 0; int i = 0; while (i < nums.length) { int currentNum = nums[i]; // Find the end of the block of currentNum int j = i; while (j < nums.length && nums[j] == currentNum) { j++; } // Calculate frequency of the current number int currentFreq = j - i; // Check if it's an even number and if its frequency is the highest so far if (currentNum % 2 == 0) { if (currentFreq > maxFreq) { maxFreq = currentFreq; ans = currentNum; } } // Move to the next distinct number i = j; } return ans; }}Complexity
Time
O(N log N), where N is the number of elements. The sorting step dominates the overall time complexity. The subsequent linear scan to count frequencies takes O(N) time.
Space
O(log N) to O(N). This depends on the implementation of the sorting algorithm used. For example, in Java, `Arrays.sort()` for primitives uses a dual-pivot quicksort, which has an average space complexity of O(log N).
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
The tie-breaking condition (smallest number) is handled naturally by iterating through the sorted array.
Cons
The time complexity is dominated by sorting, which is not as fast as a linear scan.
Sorting modifies the original array if done in-place, or requires extra space for a copy.
The most efficient approach uses a hash map (or a frequency map) to count the occurrences of each even number in a single pass. After counting, a second pass over the map's entries is performed to find the even element with the highest frequency, correctly handling ties by choosing the smallest element.
Algorithm
- Create a
HashMapto store the frequency of each even number. The key will be the even number and the value will be its frequency. - Iterate through the input array
numsonce. - For each number
numinnums:- Check if
numis even. - If it is, update its count in the
HashMap. You can usemap.put(num, map.getOrDefault(num, 0) + 1)for this.
- Check if
- After populating the map, initialize
ans = -1andmaxFreq = 0. - Iterate through the key-value pairs (entries) of the
HashMap. - For each entry (
num,freq):- If
freq > maxFreq, updatemaxFreq = freqandans = num. - If
freq == maxFreq, updateans = Math.min(ans, num)to handle the tie-breaker rule (choose the smallest number).
- If
- Finally, return
ans.
Walkthrough
This approach decouples the counting from the finding. First, we build a frequency map of all even numbers in the input array. A hash map is a perfect data structure for this, as it provides average O(1) time complexity for insertions and lookups. We iterate through nums, and for each even number, we increment its count in the map. Once the map is built, we iterate through its entries to find the one that satisfies the conditions. We keep track of the maximum frequency seen so far and the corresponding number. The tie-breaking logic is applied during this second iteration.
import java.util.HashMap;import java.util.Map; class Solution { public int mostFrequentEven(int[] nums) { Map<Integer, Integer> freqMap = new HashMap<>(); for (int num : nums) { if (num % 2 == 0) { freqMap.put(num, freqMap.getOrDefault(num, 0) + 1); } } int ans = -1; int maxFreq = 0; // Iterate through the map to find the most frequent even element for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) { int num = entry.getKey(); int freq = entry.getValue(); if (freq > maxFreq) { maxFreq = freq; ans = num; } else if (freq == maxFreq) { ans = Math.min(ans, num); } } return ans; }}Complexity
Time
O(N), where N is the number of elements in `nums`. We iterate through the array once to build the map (O(N)) and then iterate through the map's entries. The number of unique even elements is at most N, so the second iteration is also at most O(N).
Space
O(K), where K is the number of unique even elements in the array. In the worst-case scenario where all elements are unique and even, the space complexity would be O(N).
Trade-offs
Pros
Optimal time complexity of O(N).
It's a very common and effective pattern for solving frequency-based problems.
Cons
Requires extra space to store the hash map, which can be up to O(N) in the worst case.
Solutions
Solution
class Solution {public int mostFrequentEven(int[] nums) { Map<Integer, Integer> cnt = new HashMap<>(); for (int x : nums) { if (x % 2 == 0) { cnt.merge(x, 1, Integer : : sum); } } int ans = -1, mx = 0; for (var e : cnt.entrySet()) { int x = e.getKey(), v = e.getValue(); if (mx < v || (mx == v && ans > x)) { ans = x; mx = v; } } return ans; }}class Solution { public: int mostFrequentEven ( vector < int >& nums ) { unordered_map < int , int > cnt ; for ( int x : nums ) { if ( x % 2 == 0 ) { ++ cnt [ x ]; } } int ans = - 1 , mx = 0 ; for ( auto & [ x , v ] : cnt ) { if ( mx < v || ( mx == v && ans > x )) { ans = x ; mx = v ; } } return ans ; } };class Solution: def mostFrequentEven(self, nums: List[int]) -> int: cnt = Counter(x for x in nums if x % 2 == 0) ans, mx = - 1, 0 for x, v in cnt . items(): if v > mx or (v == mx and ans > x): ans, mx = x, v return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.