algoadvance

Leetcode 2404. Most Frequent Even Element

Problem Statement

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,2,4,4]. The most frequent even element is 2.

Example 2:

Input: nums = [4,4,4,9,2,4]
Output: 4
Explanation: The even elements are [4,4,4,2,4]. The most frequent even element is 4.

Example 3:

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

Clarifying Questions

1. Q: What if the input array is empty? A: If nums is empty, we should return -1.

2. Q: What is the range of values in the array? A: The array can contain any integer values within the limits of int in C++.

3. Q: What should be returned in case of multiple elements having the same highest frequency? A: If there is a tie, the smallest even element should be returned.

Strategy

1. Traverse the array to collect frequencies: We will use an unordered_map to count the frequencies of even elements.
2. Identify the most frequent even element: Track the most frequent even element and resolve ties by selecting the smallest value.
3. Edge case handling: Return -1 if there are no even elements.

Code

#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;

class Solution {
public:
    int mostFrequentEven(vector<int>& nums) {
        unordered_map<int, int> freq;
        int maxFreq = 0;
        int result = -1;

        for (int num : nums) {
            if (num % 2 == 0) {
                freq[num]++;
                if (freq[num] > maxFreq || (freq[num] == maxFreq && num < result)) {
                    maxFreq = freq[num];
                    result = num;
                }
            }
        }
        
        return result;
    }
};

Time Complexity

• O(n): We traverse the array once, and each map operation (insertion and lookup) has O(1) average time complexity.
• Space Complexity: O(n) in the worst case, for the map to store the frequency of each even element.

This approach efficiently handles the problem requirements within acceptable time complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?