Scale Engineer

Most Frequent Even Element

Easy
#2188Time: 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.
Patterns
Counting
Data structures
ArrayHash Table

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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

Complexity

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.

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem