# Most Frequent Even Element
**Difficulty:** EASY
[External](https://leetcode.com/problems/most-frequent-even-element)
Canonical: https://scaleengineer.com/dsa/problems/most-frequent-even-element
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## Problem
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] <= 105`

# Approaches
## Brute Force with Nested Loops
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   Initialize `mostFrequentEven` to -1 and `maxFrequency` to 0.
*   Iterate through the input array `nums` with an outer loop (let's say index `i`).
*   For each element `nums[i]`, check if it's an even number.
*   If `nums[i]` is even, start an inner loop (index `j`) to iterate through the entire array again to count its occurrences.
*   Let the count be `currentFrequency`.
*   After the inner loop, compare `currentFrequency` with `maxFrequency`:
    *   If `currentFrequency > maxFrequency`, it means we've found a new more frequent even number. Update `maxFrequency = currentFrequency` and `mostFrequentEven = nums[i]`.
    *   If `currentFrequency == maxFrequency`, we have a tie. According to the problem, we should choose the smaller element. So, update `mostFrequentEven = min(mostFrequentEven, nums[i])`.
*   After the outer loop completes, `mostFrequentEven` will hold the result.

## Sorting the Array
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.
**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).
**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.
### Explanation
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. 

```java
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;
    }
}
```
### Algorithm
*   First, sort the input array `nums` in 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 pointer `j` to find the end of the block of identical elements.
*   The frequency of `nums[i]` is `currentFreq = j - i`.
*   If `currentFreq > maxFreq`, we have found a new most frequent element. Update `maxFreq = currentFreq` and `ans = 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 `i` to `j` to start processing the next distinct number.
*   After the loop, return `ans`.

## Using a Hash Map for Frequency Counting
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.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   Create a `HashMap` to 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 `nums` once.
*   For each number `num` in `nums`:
    *   Check if `num` is even.
    *   If it is, update its count in the `HashMap`. You can use `map.put(num, map.getOrDefault(num, 0) + 1)` for this.
*   After populating the map, initialize `ans = -1` and `maxFreq = 0`.
*   Iterate through the key-value pairs (entries) of the `HashMap`.
*   For each entry (`num`, `freq`):
    *   If `freq > maxFreq`, update `maxFreq = freq` and `ans = num`.
    *   If `freq == maxFreq`, update `ans = Math.min(ans, num)` to handle the tie-breaker rule (choose the smallest number).
*   Finally, return `ans`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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 ; } };
```

### Python

```python
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 ans

```