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.

Clarifying Questions

1. Q: What is the range of input values for nums? A: The input array nums can contain integers ranging from -10^5 to 10^5.

2. Q: What is the length of the input array nums? A: The length of nums can be between 1 and 10^5.

3. Q: How should we handle negative even numbers? A: Negative even numbers are considered valid and should be treated like any other even number.

4. Q: Can nums contain duplicates? A: Yes, nums can contain duplicate values.

Strategy

1. Initialize an empty map to count the frequency of each even element.
2. Traverse through the array nums:
   • If an element is even, update its count in the frequency map.
3. After processing the array, iterate through the map to find the most frequent even element.
   • If there is a tie in frequency, choose the smallest element.
4. Return the most frequent even element. If no even element is found, return -1.

Code

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int mostFrequentEvenElement(int[] nums) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();

        // Step 2: Populate the frequency map with even numbers
        for (int num : nums) {
            if (num % 2 == 0) {
                frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
            }
        }

        // Step 3: Find the most frequent even element
        int mostFrequentEven = -1;
        int highestFrequency = -1;

        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            int num = entry.getKey();
            int freq = entry.getValue();

            if (freq > highestFrequency || (freq == highestFrequency && num < mostFrequentEven)) {
                highestFrequency = freq;
                mostFrequentEven = num;
            }
        }

        return mostFrequentEven;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = { 4, 2, 4, 6, 2, 4, 2 };
        System.out.println(solution.mostFrequentEvenElement(nums));  // Output: 2
    }
}

Time Complexity

• Traversing the array: O(n), where n is the length of nums.
• Populating the frequency map: O(n), as we iterate through nums.
• Finding the most frequent element: O(m), where m is the number of unique even elements in the map.

Overall, the time complexity is O(n + m), which simplifies to O(n) since m is at most n.

Space Complexity

• We use extra space for the frequency map which holds at most n/2 entries if all elements are even. Hence, the space complexity is O(n).

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?