Problem Description

You are given an integer array digits where each element is a single digit (0-9). The array may contain duplicate values.

Your task is to find all unique integers that satisfy these three conditions:

1. The integer is formed by concatenating exactly three elements from the digits array. You can pick any three elements in any order (the same element can be used multiple times if it appears multiple times in the array).

2. The integer cannot have leading zeros. This means the integer must be between 100 and 999 (inclusive).

3. The integer must be even. This means it must end with 0, 2, 4, 6, or 8.

For example, if digits = [1, 2, 3]:

• You can form 132 by using digits 1, 3, and 2
• You can form 312 by using digits 3, 1, and 2
• Both are valid because they are 3-digit numbers without leading zeros and are even

The output should be a sorted array containing all unique integers that meet these requirements.

Key Points:

• Each digit in the array can only be used as many times as it appears in the original array
• If digits = [1, 2, 2], you can form 122 or 212, but not 222 (since there's only two 2's)
• The result should contain no duplicates and be sorted in ascending order

Intuition

When we need to find all valid 3-digit even numbers that can be formed from the given digits, a natural first thought might be to generate all possible combinations of three digits. However, this would involve checking permutations and dealing with duplicates, which can get complicated.

Instead, let's think about this problem from a different angle. We know that:

• Valid numbers are between 100 and 999
• They must be even (end with 0, 2, 4, 6, or 8)
• They can only use digits available in our array

This suggests a simpler approach: why not just check every even number from 100 to 998?

For each even number in this range, we can break it down into its individual digits and check if we have enough of each digit in our original array. This is like asking: "Can I build this number using the digits I have available?"

Think of it like having a bag of digit tiles. For each even number from 100 to 998:

• Break the number into its three digits (e.g., 234 → 2, 3, 4)
• Check if we have enough of each required digit in our bag
• If yes, this number is valid

To efficiently check if we have enough digits, we can:

1. Count how many times each digit appears in our original array (store in cnt)
2. For each candidate number, count what digits it needs (store in cnt1)
3. Compare: do we have at least as many of each digit as needed?

This approach is elegant because it avoids the complexity of generating combinations and automatically handles uniqueness - we're checking each possible number exactly once.

Learn more about Sorting patterns.

Solution Approach

Following our intuition, we implement the solution using a counting and enumeration strategy:

Step 1: Count Available Digits

cnt = Counter(digits)

We use Python's Counter to count how many times each digit (0-9) appears in the input array. This gives us our "inventory" of available digits.

Step 2: Initialize Result Array

ans = []

This will store all valid even numbers we find.

Step 3: Enumerate Even Numbers

for x in range(100, 1000, 2):

We iterate through all even numbers from 100 to 998. The step size of 2 ensures we only check even numbers (100, 102, 104, ..., 998).

Step 4: Extract and Count Digits of Current Number

cnt1 = Counter()
y = x
while y:
    y, v = divmod(y, 10)
    cnt1[v] += 1

For each candidate number x:

• Create a new counter cnt1 to track what digits this number needs
• Use divmod(y, 10) to extract digits one by one:
  • v gets the last digit (remainder when divided by 10)
  • y becomes the number with the last digit removed (quotient)
  • Add each extracted digit to cnt1

For example, if x = 234:

• First iteration: y = 23, v = 4, so cnt1[4] = 1
• Second iteration: y = 2, v = 3, so cnt1[3] = 1
• Third iteration: y = 0, v = 2, so cnt1[2] = 1

Step 5: Check Availability

if all(cnt[i] >= cnt1[i] for i in range(10)):
    ans.append(x)

We check if we have enough of each digit (0-9) to form the current number:

• For each digit i from 0 to 9, verify that cnt[i] >= cnt1[i]
• This means we have at least as many of digit i as needed
• If all digits pass this check, the number is valid and we add it to our answer

Step 6: Return Result

return ans

The answer array is already sorted because we enumerated numbers in ascending order.

Time Complexity: O(1) - We check at most 450 even numbers (from 100 to 998), and for each number, we perform constant-time operations.

Space Complexity: O(1) - The counters store at most 10 digits, which is constant space.

Example Walkthrough

Let's walk through the solution with digits = [2, 2, 8, 8, 2].

Step 1: Count Available Digits

cnt = {2: 3, 8: 2}  # We have three 2's and two 8's

Step 2: Check Even Numbers from 100-998

Let's trace through a few numbers:

Checking x = 222:

• Extract digits: 222 → needs {2: 3}
• Compare with available: We have {2: 3}, need {2: 3}
• ✓ Valid! Add 222 to result

Checking x = 224:

• Extract digits: 224 → needs {2: 2, 4: 1}
• Compare with available: We have {2: 3} but no 4's
• ✗ Invalid (missing digit 4)

Checking x = 228:

• Extract digits: 228 → needs {2: 2, 8: 1}
• Compare with available: We have {2: 3, 8: 2}
• ✓ Valid! Add 228 to result

Checking x = 282:

• Extract digits: 282 → needs {2: 2, 8: 1}
• Compare with available: We have {2: 3, 8: 2}
• ✓ Valid! Add 282 to result

Checking x = 288:

• Extract digits: 288 → needs {2: 1, 8: 2}
• Compare with available: We have {2: 3, 8: 2}
• ✓ Valid! Add 288 to result

Checking x = 822:

• Extract digits: 822 → needs {8: 1, 2: 2}
• Compare with available: We have {2: 3, 8: 2}
• ✓ Valid! Add 822 to result

Checking x = 828:

• Extract digits: 828 → needs {8: 2, 2: 1}
• Compare with available: We have {2: 3, 8: 2}
• ✓ Valid! Add 828 to result

Checking x = 882:

• Extract digits: 882 → needs {8: 2, 2: 1}
• Compare with available: We have {2: 3, 8: 2}
• ✓ Valid! Add 882 to result

Checking x = 888:

• Extract digits: 888 → needs {8: 3}
• Compare with available: We have {8: 2} but need {8: 3}
• ✗ Invalid (not enough 8's)

Final Result: [222, 228, 282, 288, 822, 828, 882]

The result is automatically sorted since we checked numbers in ascending order.

Solution Implementation

Time and Space Complexity

Time Complexity: O(k × 10^k) where k = 3 is the number of digits in the target even numbers.

The algorithm iterates through all even numbers from 100 to 998 (inclusive), which gives us 450 iterations. For each number x, it extracts digits using a while loop that runs k times (3 times for 3-digit numbers). Inside the loop, there's a divmod operation which is O(1). After extracting digits, it checks if all 10 possible digits (0-9) satisfy the condition cnt[i] >= cnt1[i], which takes O(10) = O(1) time.

Therefore, the total time complexity is O(450 × 3) = O(1350) = O(k × 10^k) where 10^k represents the range of k-digit numbers and the constant factor accounts for checking only even numbers and the digit extraction process.

Space Complexity: O(1) (excluding the space for the answer array)

The algorithm uses:

• cnt: A Counter object storing at most 10 key-value pairs (digits 0-9), which is O(1)
• cnt1: Another Counter object also storing at most 10 key-value pairs, which is O(1)
• A few integer variables (x, y, v), each taking O(1) space

The answer array ans can contain at most O(10^k) elements, but as stated in the reference, we exclude this from the space complexity analysis. Thus, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding Digit Usage Constraints

The Problem: A common mistake is thinking that each position in the array can only be used once, rather than understanding that each digit VALUE can be used up to the number of times it appears.

Incorrect Approach:

# WRONG: Trying to use array indices/positions
def findEvenNumbers(self, digits: List[int]) -> List[int]:
    result = []
    n = len(digits)
    # This generates combinations of indices, not digit values
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if i != j and j != k and i != k:  # Wrong constraint!
                    num = digits[i] * 100 + digits[j] * 10 + digits[k]
                    if num >= 100 and num % 2 == 0:
                        result.append(num)
    return sorted(list(set(result)))

Why It's Wrong: If digits = [1, 2, 2], this approach wouldn't allow forming 221 because it requires using the digit 2 twice, but the index-based approach prevents reusing any position.

Correct Understanding: Count the frequency of each digit value. If you have two 2's in the array, you can use the digit 2 up to twice when forming a number.

Pitfall 2: Inefficient Permutation Generation

The Problem: Generating all possible 3-digit permutations first, then filtering for validity leads to duplicate work and complexity.

Inefficient Approach:

# INEFFICIENT: Generate all permutations first
def findEvenNumbers(self, digits: List[int]) -> List[int]:
    from itertools import permutations
    result = set()
  
    # This generates many duplicate combinations
    for perm in permutations(digits, 3):
        num = perm[0] * 100 + perm[1] * 10 + perm[2]
        if num >= 100 and num % 2 == 0:
            result.add(num)
  
    return sorted(list(result))

Why It's Inefficient:

• For digits = [1, 1, 2, 2, 3, 3], this generates 6×5×4 = 120 permutations
• Many permutations form the same number (e.g., using the first 1 vs the second 1)
• We check many odd numbers and numbers with leading zeros unnecessarily

Better Solution: The provided approach iterates through only the 450 possible even 3-digit numbers and checks if each can be formed.

Pitfall 3: Forgetting Edge Cases with Zeros

The Problem: Not properly handling zeros, especially when they appear multiple times.

Problematic Scenario:

# Example that might cause issues:
digits = [0, 0, 2]
# Can form: 200 (valid)
# Cannot form: 002 (has leading zero, not a valid 3-digit number)

Key Points to Remember:

• A 3-digit number cannot start with 0 (must be 100-999)
• Zero can appear in the middle or end position
• If you need multiple zeros (like in 200), ensure you have enough zeros in the input

The solution correctly handles this by only checking numbers in range(100, 1000, 2), automatically excluding numbers with leading zeros.