Leetcode 2404: Most Frequent Even Element

Input: You are given an integer array `nums` containing elements from 0 to 100,000.

Example: nums = [1, 3, 5, 2, 4, 4, 4]

Constraints:

• 1 <= nums.length <= 2000

• 0 <= nums[i] <= 10^5

Output: Return the most frequent even element in the array. If no even element exists, return -1.

Example: Output: 4

Constraints:

Goal: The goal is to find the most frequent even element, and in case of a tie, return the smallest one.

Steps:

• 1. Create a map (hash table) to count the frequency of each element in the array.

• 2. Loop through the map and identify the most frequent even element.

• 3. If there is a tie in frequency, select the smallest element.

• 4. If no even element is found, return -1.

Goal: Ensure that the solution efficiently handles arrays of sizes up to 2000 with integer elements in the range 0 to 100,000.

Steps:

• The solution should run in linear time relative to the size of the input array.

Assumptions:

• The input array is valid and consists only of non-negative integers.

• Input: nums = [0, 1, 2, 2, 4, 4, 1]

• Explanation: The even elements in the array are 0, 2, and 4. Both 2 and 4 appear the most times, but since 2 is smaller, it is returned.

• Input: nums = [3, 5, 7, 9]

• Explanation: There are no even elements in the array, so the result is -1.

• Input: nums = [4, 4, 4, 9, 2, 4]

• Explanation: The even element 4 appears most frequently, so it is returned.

Approach: To solve this problem, we can use a hash map to count the frequency of each element in the array and then determine the most frequent even element.

Observations:

• We can iterate over the array to count the occurrences of each element.

• We need to check if the element is even and then compare its frequency to keep track of the most frequent even element.

• Efficiently counting frequencies using a hash map and checking conditions will help us solve the problem in linear time.

Steps:

• 1. Create a hash map to store the frequency of each element.

• 2. Iterate through the array and update the frequency count for each element.

• 3. Iterate through the map and track the most frequent even element. If there is a tie, return the smallest element.

• 4. If no even element is found, return -1.

Empty Inputs:

• This problem does not have an empty input case as the array length is guaranteed to be at least 1.

Large Inputs:

• The solution should efficiently handle arrays with sizes up to 2000 and elements in the range of 0 to 100,000.

Special Values:

• If no even element exists in the array, return -1.

Constraints:

• The solution must be efficient with a time complexity of O(n) due to the array's potential size.

int mostFrequentEven(vector<int>& nums) {
    map<int, int> mp;
    for(auto n: nums) mp[n]++;
    int ans = -1, mx = -1;
    for(auto m: mp){
        if(m.first%2 == 0 && m.second > mx){
            mx = m.second;
            ans = m.first;
        }
    }
    return ans;
}

1 : Function Declaration

int mostFrequentEven(vector<int>& nums) {

This is the function signature for `mostFrequentEven`, which takes a reference to a vector of integers `nums`.

2 : Map Initialization

    map<int, int> mp;

Initialize a map `mp` where the key is an integer from the array, and the value is its frequency of occurrence.

3 : Frequency Counting

    for(auto n: nums) mp[n]++;

Iterate through the `nums` array, counting the frequency of each number and storing it in the map `mp`.

4 : Variable Initialization

    int ans = -1, mx = -1;

Initialize variables `ans` to store the answer (set to -1 initially), and `mx` to track the maximum frequency of any number (also set to -1).

5 : Loop Through Map

    for(auto m: mp){

Loop through each key-value pair in the map `mp`, where `m.first` is the number and `m.second` is its frequency.

6 : Condition Check for Even Numbers

        if(m.first%2 == 0 && m.second > mx){

Check if the number is even (`m.first % 2 == 0`) and if its frequency `m.second` is greater than the current maximum frequency `mx`.

7 : Update Maximum Frequency

            mx = m.second;

Update the maximum frequency `mx` to the frequency of the current even number.

8 : Update Answer

            ans = m.first;

Update the answer `ans` to the current even number `m.first` with the highest frequency.

9 : Return Statement

    return ans;

Return the answer `ans`, which is the most frequent even number or -1 if no such number exists.

Best Case: O(n), where n is the length of the array, since we only need to pass through the array once and then through the map.

Average Case: O(n), as we still process each element in the array once and use the map in linear time.

Worst Case: O(n), as both counting frequencies and comparing map entries are linear operations.

Description: The solution runs in linear time, making it optimal for this problem.

Best Case: O(1), if there are no even elements or only one unique element in the array.

Worst Case: O(n), as we store the frequency of each unique element in the array in a hash map.

Description: The space complexity is linear, as we store the frequencies of the elements in a hash map.

Leetcode 2404: Most Frequent Even Element

Explore →