LeetCode 3866 - First Unique Even Element

LeetCode Problem 3866

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Counting

Solution

Problem Understanding

The problem asks us to find the first even integer in an array that appears exactly once. In other words, we need to traverse the array and identify even numbers, count their occurrences, and return the earliest one that occurs only a single time. If there is no such even number, we return -1.

The input nums is a list of integers ranging from 1 to 100, and its length is between 1 and 100. These constraints imply the input is small, so we can afford solutions that are quadratic in nature, but a linear solution is preferable and more elegant. Edge cases include arrays with no even numbers, arrays where all even numbers appear more than once, and arrays where the first even number occurs more than once but a later even number occurs only once.

Approaches

Brute Force Approach

The brute force approach iterates through each element in the array. For every even number, it counts how many times that number appears in the entire array. If the count is exactly one, it returns that number. Otherwise, it continues. This works because it explicitly checks each even number for uniqueness, but it is inefficient because counting occurrences for each number requires scanning the entire array repeatedly.

Optimal Approach

The optimal approach leverages a hash map (dictionary in Python) to count the occurrences of each number in a single pass. After counting, we make a second pass over the array to find the first even number with a count of exactly one. This ensures linear time complexity while maintaining the original order of elements, which is crucial because the first unique even element is determined by array index.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Count occurrences of each even number individually
Optimal	O(n)	O(n)	Use a hash map to count all numbers, then scan array once

Algorithm Walkthrough

1. Initialize an empty dictionary count to track the occurrences of each number.
2. Traverse the array nums. For each number num, increment its count in the dictionary. This allows us to know how many times each number appears without multiple scans.
3. Traverse the array nums a second time. For each number num, check if it is even (num % 2 == 0) and its count in the dictionary is exactly 1.
4. Return the first number that satisfies both conditions. If no number satisfies the conditions after traversing the array, return -1.

Why it works: The hash map guarantees we know the exact count of every number. By scanning the array in order after counting, we preserve the original index order, ensuring the "first" unique even number is returned. The invariant is that every number’s count is accurate before we attempt to find the result.

Python Solution

class Solution:
    def firstUniqueEven(self, nums: list[int]) -> int:
        count = {}
        for num in nums:
            count[num] = count.get(num, 0) + 1
        
        for num in nums:
            if num % 2 == 0 and count[num] == 1:
                return num
        
        return -1

The implementation first constructs a dictionary count to store how many times each number appears. It then iterates through nums in the original order to check for even numbers with a count of 1. The first number meeting both conditions is returned immediately. If no such number exists, -1 is returned.

Go Solution

func firstUniqueEven(nums []int) int {
    count := make(map[int]int)
    for _, num := range nums {
        count[num]++
    }
    
    for _, num := range nums {
        if num%2 == 0 && count[num] == 1 {
            return num
        }
    }
    
    return -1
}

In Go, we use a map to count occurrences of each integer. The logic mirrors the Python version, ensuring linear time complexity and preserving array order. Go does not differentiate between nil and empty maps during counting, and integer overflow is not a concern given the constraints.

Worked Examples

Example 1

Input: nums = [3,4,2,5,4,6]

First pass to count occurrences:

Number	Count
3	1
4	2
2	1
5	1
6	1

Second pass to find first unique even:

Number	Condition	Result
3	odd	skip
4	even, count=2	skip
2	even, count=1	return 2

Output: 2

Example 2

Input: nums = [4,4]

Counts:

Number	Count
4	2

No even number with count 1, return -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Two passes over the array: one for counting, one for checking
Space	O(n)	Hash map stores counts for up to n elements

Even though the array size is small (up to 100), the linear solution is clean, efficient, and generalizable to larger inputs.

Test Cases

# Provided examples
assert Solution().firstUniqueEven([3,4,2,5,4,6]) == 2  # first unique even is 2
assert Solution().firstUniqueEven([4,4]) == -1         # no unique even number

# Edge cases
assert Solution().firstUniqueEven([1,3,5,7]) == -1    # no even numbers
assert Solution().firstUniqueEven([2,4,2,6,4,8]) == 6 # first unique even is 6
assert Solution().firstUniqueEven([2]) == 2           # single element even number
assert Solution().firstUniqueEven([1]) == -1          # single element odd number
assert Solution().firstUniqueEven([2,2,2,2]) == -1    # repeated even numbers only

Test	Why
[3,4,2,5,4,6]	Tests multiple unique even numbers, returns earliest
[4,4]	Tests no unique even numbers
[1,3,5,7]	Tests no even numbers at all
[2,4,2,6,4,8]	Tests skipping repeated even numbers to find first unique
[2]	Single element array with even number
[1]	Single element array with odd number
[2,2,2,2]	Multiple repeated even numbers only

Edge Cases

Case 1: No even numbers. An array like [1,3,5,7] could cause naive implementations to return an incorrect value. Our solution correctly checks for num % 2 == 0 and will return -1.

Case 2: All even numbers repeated. In [2,2,4,4], the first even number is repeated, so we must continue scanning. The hash map ensures counts are tracked properly and no repeated number is incorrectly returned.

Case 3: Single-element array. Arrays with one element, [2] or [1], test the algorithm’s ability to handle minimal input sizes. The solution correctly returns the element if it is a unique even or -1 otherwise.