LeetCode 2404 - Most Frequent Even Element

The problem asks us to identify the most frequent even number in an integer array nums. If multiple even numbers share the highest frequency, we should return the smallest among them. If the array contains no even numbers, the function should return -1.

leetcodeeasyarrayhash-tablecounting

LeetCode Problem 2404

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Counting

Solution

Problem Understanding

The problem asks us to identify the most frequent even number in an integer array nums. If multiple even numbers share the highest frequency, we should return the smallest among them. If the array contains no even numbers, the function should return -1.

The input array nums can have up to 2000 elements, each ranging from 0 to 105. This tells us that the array is relatively small, so a linear or near-linear solution is feasible. The constraints also guarantee non-negative integers, which simplifies edge case handling related to negative numbers.

Important edge cases include arrays with no even numbers, arrays where multiple even numbers have the same highest frequency, and arrays where all numbers are even or all numbers are odd. Handling ties correctly and returning -1 when no even numbers exist are critical for correctness.

Approaches

The brute-force approach would involve iterating over the array for each even number to count its occurrences and then comparing counts to find the maximum frequency. This would involve a nested iteration, which is unnecessary given the constraints and the ability to use hash tables for counting.

The optimal solution uses a hash map (dictionary in Python or map in Go) to count the frequency of each even number in a single pass. After building the frequency map, we iterate over it to determine the even number with the highest frequency, breaking ties by choosing the smallest number. This approach leverages the counting property of hash maps for efficient frequency tracking.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Count occurrences by iterating over the array for each even number. Inefficient for larger arrays.
Optimal O(n) O(n) Use a hash map to count occurrences of even numbers and select the most frequent smallest one in a single pass.

Algorithm Walkthrough

  1. Initialize an empty hash map to store frequencies of even numbers.
  2. Iterate through each number in the array. For each number, check if it is even.
  3. If the number is even, increment its count in the hash map. Ignore odd numbers.
  4. Initialize two variables: max_freq to track the maximum frequency observed, and result to store the smallest even number with this frequency.
  5. Iterate through the hash map. For each key-value pair, compare the frequency to max_freq.
  6. If the frequency is higher than max_freq, update max_freq and set result to the current number.
  7. If the frequency equals max_freq and the current number is smaller than result, update result to the current number.
  8. After iterating through the map, check if result was updated. If no even number was found, return -1. Otherwise, return result.

Why it works: This algorithm works because it counts all even numbers exactly once and stores their frequencies efficiently. By tracking the maximum frequency and the smallest number in case of ties, it guarantees correctness while maintaining linear time complexity.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def mostFrequentEven(self, nums: List[int]) -> int:
        freq = defaultdict(int)
        for num in nums:
            if num % 2 == 0:
                freq[num] += 1

        max_freq = 0
        result = -1
        for num, count in freq.items():
            if count > max_freq or (count == max_freq and num < result):
                max_freq = count
                result = num

        return result

The Python solution first constructs a frequency map using defaultdict(int) to avoid key errors. The iteration over the input array ensures that only even numbers are counted. After the map is built, we traverse the map to find the highest frequency and resolve ties by choosing the smallest number. Returning -1 if no even numbers exist handles the edge case of an array without even numbers.

Go Solution

func mostFrequentEven(nums []int) int {
    freq := make(map[int]int)
    for _, num := range nums {
        if num%2 == 0 {
            freq[num]++
        }
    }

    maxFreq := 0
    result := -1
    for num, count := range freq {
        if count > maxFreq || (count == maxFreq && (result == -1 || num < result)) {
            maxFreq = count
            result = num
        }
    }

    return result
}

In Go, we use a map to track the frequency of even numbers. The key difference is that Go requires explicit handling of the initial state for the smallest number, so we check if result is -1 before comparing sizes. Otherwise, the logic mirrors the Python solution.

Worked Examples

Example 1: nums = [0,1,2,2,4,4,1]

Step freq map max_freq result
0 {} 0 -1
0 (even) {0:1} 1 0
1 (odd) {0:1} 1 0
2 (even) {0:1,2:1} 1 0
2 (even) {0:1,2:2} 2 2
4 (even) {0:1,2:2,4:1} 2 2
4 (even) {0:1,2:2,4:2} 2 2 (tie, smallest number)
1 (odd) {0:1,2:2,4:2} 2 2

Output: 2

Example 2: nums = [4,4,4,9,2,4]

Output: 4 (frequency 4 > frequency 2)

Example 3: nums = [29,47,21,41,13,37,25,7]

Output: -1 (no even numbers)

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate over the array once to build the frequency map and once over the map to determine the maximum frequency.
Space O(n) In the worst case, all numbers are unique and even, so the map stores n entries.

The reasoning is straightforward: every number is processed exactly once for counting and then every distinct even number is checked to find the result.

Test Cases

# provided examples
assert Solution().mostFrequentEven([0,1,2,2,4,4,1]) == 2  # tie, smallest even returned
assert Solution().mostFrequentEven([4,4,4,9,2,4]) == 4     # single most frequent even
assert Solution().mostFrequentEven([29,47,21,41,13,37,25,7]) == -1  # no even

# additional edge cases
assert Solution().mostFrequentEven([2,2,4,4]) == 2         # tie, smallest even
assert Solution().mostFrequentEven([0]) == 0               # single even
assert Solution().mostFrequentEven([1]) == -1              # single odd
assert Solution().mostFrequentEven([2,4,6,8,2,4,6,8,8]) == 8  # multiple frequencies
assert Solution().mostFrequentEven([]) == -1              # empty input (edge case)
Test Why
[0,1,2,2,4,4,1] Tie in frequency, check smallest selection
[4,4,4,9,2,4] Most frequent even number exists
[29,47,21,41,13,37,25,7] No even numbers, should return -1
[2,2,4,4] Tie resolution by smallest number
[0] Single even number
[1] Single odd number, returns -1
[2,4,6,8,2,4,6,8,8] Multiple even numbers with different frequencies
[] Empty input array

Edge Cases

One important edge case is when the array contains no even numbers, such as [1,3,5]. Without careful handling, the algorithm could incorrectly return 0 or some uninitialized value. Our solution explicitly initializes result to -1 and only updates it for even numbers, ensuring correct output.

Another edge case is when multiple even numbers share the maximum frequency. For example, [2,2,4,4] has a tie between 2 and 4. The algorithm correctly resolves this by selecting the smallest even number.

A third edge case is arrays with a single element, either even or odd. The algorithm handles these naturally since the counting loop and final selection logic are robust to arrays of length 1. For [0] it returns 0, and for [1] it returns -1. This ensures no special branching is required for very small arrays.