LeetCode › 3866. First Unique Even Element › Chapter 1
CHAPTER 1 OF 1

3866. First Unique Even Element

We iterate from a manual counts dict through `Counter` to a one-pass dict-as-ordered-set, then land on Counter filtered by a generator. Readable over clever when the complexity is the same.

Problem

You are given an integer array nums.

Return an integer denoting the first even integer (earliest by array index) that appears exactly once in nums. If no such integer exists, return -1.

An integer x is considered even if it is divisible by 2.

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

Examples:

  • nums = [3, 4, 2, 5, 4, 6] → 2. Both 2 and 6 are even and appear exactly once; 2 comes first.
  • nums = [4, 4] → -1. No even integer appears exactly once.

Walkthrough

Two-pass

We'll start with a sub-optimal two-pass solution as it is easier to get right and shows you understand the problem. We can do one pass over the list counting how many instances of each variable we have. Then do a second pass looking at the counts and returning the first one where there is a count of 1. We'll manually construct our counts in a dictionary for this version. Don't forget that the problem only asks for even integers, so we can ignore all the odd ones. To check if a number is odd we'll use the modulo operator % which tells us the remainder after dividing by a number. So x % 2 will be 0 if it's even and 1 if it's odd.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def firstUniqueEven(self, nums: list[int]) -> int:
    counts = {}

    # First pass construct the counts
    for value in nums:
      if value not in counts:
        counts[value] = 0
      counts[value] += 1

    # Second pass locate the first with a count of 1.
    for value in nums:
      # Skip odd numbers
      if (value % 2) == 1:
        continue
      # If the count is 1 we're done
      if counts[value] == 1:
        return value

    # If nothing found we return -1
    return -1
Submission result Two-pass submission result on LeetCode

I didn't add the skip for odd numbers to the construction of the counts, you could have added that there too.

This is O(n) time complexity, we do two passes through the list: one to construct the counts and one to look for a count of 1 on even integers. Space complexity is O(n) too as we need to maintain the count dictionary.

Counter

We built our own counter function here, but you could also have used the inbuilt one from the collections package. There's no point reinventing the wheel when the builtin solutions exist.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
from collections import Counter
class Solution:
  def firstUniqueEven(self, nums: list[int]) -> int:
    counts = Counter(nums)

    # Second pass locate the first with a count of 1.
    for value in nums:
      # Skip odd numbers
      if (value % 2) == 1:
        continue
      # If the count is 1 we're done
      if counts[value] == 1:
        return value

    # If nothing found we return -1
    return -1
Submission result Counter submission result on LeetCode

This doesn't change the complexity at all, it's just using an inbuilt function rather than us coding it up ourselves.

Without revisiting nums

Now we have a two-pass solution the natural question is can we do this in a single pass without revisiting the nums array. One way we could look to do this is rather than explicitly counting we could just keep track of numbers we've seen. If we do this then when we see a number we've already seen we know it isn't the answer. We could do this with a set which obviously stores unique elements only. We'd need two sets really. One storing the values we've seen just once and one storing the values we've seen multiple times. First time we see a value we add it to the seen_once set, then if we see it again we can move it to the seen_multiple one.

The problem with this though is that, once we've constructed those sets, we still have to go through nums to find the first one. This is because a set doesn't preserve insertion order. However, we can get the same functionality with a dict - these do preserve insertion order. We don't actually want the value associated with the dict, we'll just arbitrarily assign them True.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
  def firstUniqueEven(self, nums: list[int]) -> int:
    # Dicts preserve insertion order
    seen_once = dict()
    seen_multiple = set()

    # One pass through the numbers
    for value in nums:
      # Skip odd numbers
      if (value % 2) == 1:
        continue
      # Carry on if we've seen it multiple times before
      if value in seen_multiple:
        continue
      # If we've only seen it once, we need to move it from the dict to the set.
      if value in seen_once:
        del seen_once[value]
        seen_multiple.add(value)
        continue
      # Else this is the first time we've seen it.
      seen_once[value] = True

    # Read off the answer if there is one, else -1.
    return next(iter(seen_once), -1)
Submission result Without-revisiting-nums submission result on LeetCode

Note the del is how we remove a key from a dictionary. The final next(iter(...)) just pulls off the first value, it's not a full pass through the data, it's just getting the first element or our default of -1.

We haven't changed the asymptotic complexity here it's still O(n) time as we have to go through the list, and it's still O(n) space as with unique values we store everything in our sets. But we have removed the second pass through the unique elements. But added complexity in the set management.

Desired solution

With all things considered this would be my desired solution. We can tidy up the Counter to only count the even numbers by passing in a generator expression rather than just counting everything.

As the counter is essentially a dict, they preserve insertion order too. Iterating over the dict we can look for the first 1.

This second iteration is at most n but it's actually the number of unique even elements in the list which for most inputs would be less.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
from collections import Counter

class Solution:
  def firstUniqueEven(self, nums: list[int]) -> int:
    # Only count the even numbers
    counts = Counter(v for v in nums if v % 2 == 0)

    # The counter preserves insertion order
    for value, count in counts.items():
      if count == 1:
        return value

    # Fall back for no unique even numbers.
    return -1
Submission result Desired solution submission result on LeetCode

This solution is still O(n) time complexity, and O(n) space complexity. It's the most readable and maintainable solution though in my opinion. It's not worth all the extra complexity of the seen sets.

Back to course →