Apr 17, 2024 - 4 min read

Rust LeetCode: 2404. Most Frequent Even Element

Even the Odds: Untangling Vectors with Rust

Problem Statment

2404. Most Frequent Even Element presented as follows: 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 that 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

Intuition

The task is to find the most frequent even number in an array or vector in our case with Rust. If multiple even numbers have the highest frequency, we return the smallest among them. The challenge involves efficiently counting occurrences while considering the parity of the numbers. Using a HashMap enables us to count each even number's occurrences as we iterate through the array. Once populated, we can determine which even number(s) occur most frequently and resolve ties by selecting the smallest number. This approach is both intuitive and efficient for the constraints provided.

Approach

As usual we'll approach this in 2 different ways, although both use HashMaps we'll have a more straightforward imperative way, with a more functional approach that uses some of Rust's method's.

Code

Imperative Solution

use std::collections::HashMap;

fn most_freq_even(nums: Vec<i32>) -> i32 {
    let mut hm = HashMap::new();

    for i in nums {
        if i % 2 == 0 {
            let count = hm.entry(i).or_insert(0);
            *count += 1;
        }
    }

    let mut freq = -1;
    let mut max = 0;

    for (k, v) in hm {
        if v > max || (v == v && k < freq){
            freq = k;
            max = v;
        }
    }
    freq
}
fn main() {
    println!("{}", most_freq_even(vec![2, 2, 2, 4, 4, 4]));
}

Functional

use std::collections::HashMap;

fn most_freq_even(nums: Vec<i32>) -> i32 {

    let hm = nums.into_iter()
        .filter(|i| i % 2 == 0)
        .fold(HashMap::new(), |mut acc, i|{
            *acc.entry(i).or_insert(0) += 1;
            acc
        });

    hm.into_iter()
        .fold((-1, 0), |(freq, max), (k, v)|{
            if v > max || (v == max && k < freq){
                (k,v)
            } else {
                (freq, max)
            }
        }).0
}
fn main() {
    println!("{}", most_freq_even(vec![2, 2, 2, 4, 4, 4]));
}

Explanation

As previously stated the solutions are implemented in Rust, using its powerful HashMap collection to track the counts of even numbers.

  1. Imperative Solution: This approach involves iterating through the array, filtering even numbers, and counting their occurrences using a hash map. After constructing the hash map, another pass through the map's keys allows us to determine the most frequent even element. We check each key-value pair, updating our result if we find a higher count or a smaller number with the same count. This method straightforwardly handles counting and comparison in separate steps.

  2. Functional Solution: Here, the solution leverages Rust’s functional programming features, such as into_iter, filter, and fold, to achieve the same task in a more condensed form. The into_iter and filter functions build an iterator of even numbers, which fold uses to populate a hash map. Another fold operation determines the most frequent even element by comparing counts directly within the tuple manipulation, streamlining the process into a more declarative form.

Both methods efficiently use HashMap to address the problem, with the imperative method being more transparent in its steps and the functional method providing a more elegant and concise solution.

Complexity Analysis

Now let's review the time and space complexity for each of these solutions.

Time Complexity:

  1. Imperative Solution:

    • Iteration to build the hash map: We iterate through the vector once, examining each element to determine if it is even and, if so, updating its count in the hash map. This operation takes (O(n)) time, where (n) is the length of the vector.
    • Iteration to find the most frequent even element: After building the hash map, we iterate through it to find the most frequent even element. In the worst case, if all elements in the array are even and unique, the size of the hash map could be as large as (O(n)). However, typically, the number of unique elements (and thus the number of hash map entries) is much less than (n). Still, the complexity of this step is (O(u)), where (u) is the number of unique even numbers in the vector.
    • Total Time Complexity: (O(n + u)), which simplifies to (O(n)) assuming (u \leq n).

  2. Functional Solution:

    • Building the hash map using fold: Similar to the imperative solution, the functional approach filters even numbers and populates the hash map in a single pass, with a time complexity of (O(n)).
    • Finding the most frequent number using another fold: The second fold operation that determines the most frequent even number has the same (O(u)) complexity as in the imperative solution.
    • Total Time Complexity: (O(n + u)), which also simplifies to (O(n)).

Space Complexity:

  • Both Solutions:
    • Hash Map Storage: The space complexity is dominated by the hash map that stores the counts of even numbers. In the worst case, where all elements are even and unique, the space required would be (O(n)). More typically, the space complexity will be (O(u)), where (u) is the number of unique even numbers in the vector.
    • Total Space Complexity: (O(u)), which could be at most (O(n)) in a scenario where all numbers are unique and even.

Conclusion

Both the imperative and functional approaches effectively solve the problem of finding the most frequent even number in an array. The use of HashMap allows for efficient counting of elements, and the logic to determine the smallest frequent even number ensures that all criteria of the problem statement are met. These solutions demonstrate not only the utility of hash maps in frequency counting tasks but also the versatility of Rust's programming paradigms. This problem serves as an excellent example of how different approaches can be used to solve a problem efficiently while adhering to the constraints and requirements specified.