LeetCode 2094 - Finding 3-Digit Even Numbers
The problem gives us an array named digits, where every element is a single decimal digit from 0 to 9. We must use exactly three elements from this array to build valid three digit integers.
Difficulty: 🟢 Easy
Topics: Array, Hash Table, Recursion, Sorting, Enumeration
Solution
Problem Understanding
The problem gives us an array named digits, where every element is a single decimal digit from 0 to 9. We must use exactly three elements from this array to build valid three digit integers.
The important detail is that each digit can only be used as many times as it appears in the input. For example, if the array contains only one 2, then we cannot build a number like 222. If the array contains three 2s, then such a number becomes valid.
The generated number must satisfy three conditions:
- It must contain exactly three digits.
- It cannot start with
0, because leading zeros are not allowed in three digit integers. - It must be even, meaning its last digit must be
0,2,4,6, or8.
The task is to return all unique valid numbers in sorted ascending order.
The constraints are relatively small:
3 <= digits.length <= 1000 <= digits[i] <= 9
Although the input array may contain up to 100 elements, there are only 10 possible digit values. This is a very important observation because it allows us to think in terms of digit frequencies instead of worrying about large input sizes.
Several edge cases are important:
- Arrays containing only odd digits, which produce no valid even numbers.
- Arrays containing many zeros, where leading zero handling becomes critical.
- Arrays with duplicates, where we must avoid duplicate results.
- Cases where a valid number requires repeated digits, meaning frequency counting must be handled correctly.
- Inputs where all digits are the same.
A naive implementation can easily make mistakes by:
- Allowing numbers like
012 - Reusing digits more times than available
- Returning duplicate numbers
- Forgetting to sort the result
Approaches
Brute Force Approach
The most direct solution is to generate every possible selection of three indices from the array and form numbers from them.
We can use three nested loops:
- The first loop chooses the hundreds digit
- The second loop chooses the tens digit
- The third loop chooses the ones digit
For every triplet of indices:
- Ensure all indices are different
- Reject numbers with leading zero
- Reject odd numbers
- Add valid numbers to a set to avoid duplicates
This approach is correct because it explicitly checks every possible three digit arrangement that can be formed from the array.
However, the time complexity is high. Since the array length can be up to 100, three nested loops require up to 100^3 = 1,000,000 iterations. While this is still manageable for the given constraints, it is not elegant and performs unnecessary repeated work.
Optimal Approach
A better solution takes advantage of the fact that there are only 900 possible three digit numbers, from 100 to 999.
Instead of generating numbers from the digits, we can reverse the process:
- Enumerate every three digit even number
- Check whether the digits required to build that number exist in the input
To do this efficiently:
- Count the frequency of every digit in the input.
- Iterate through all even numbers from
100to998. - Extract the hundreds, tens, and ones digits.
- Check whether the input contains enough copies of each digit.
This works well because:
- There are only 450 even three digit numbers.
- Frequency checking is constant time.
- The result is naturally sorted because we iterate in ascending order.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n³) | O(k) | Generates all index combinations and removes duplicates using a set |
| Optimal | O(n + 900) | O(1) | Enumerates valid candidates and checks digit frequencies |
Algorithm Walkthrough
Optimal Algorithm
- Create a frequency array of size 10.
Since digits range only from 0 to 9, we store how many times each digit appears. For example, if the input is [2,2,8], then:
count[2] = 2count[8] = 1
This allows constant time availability checks.
2. Iterate through every even number from 100 to 998.
We increment by 2 because only even numbers are valid.
3. Extract the three digits of the current number.
For a number num:
- Hundreds digit:
num // 100 - Tens digit:
(num // 10) % 10 - Ones digit:
num % 10
- Count how many times each digit is required.
Some numbers reuse digits. For example:
288requires one2and two8s.222requires three2s.
We build another frequency array representing the current number. 5. Compare required frequencies against available frequencies.
If every required digit count is less than or equal to the available count from the input array, then the number is valid. 6. Add the valid number to the result list.
Because we iterate in ascending order, the result list is already sorted. 7. Return the result list after all numbers are checked.
Why it works
The algorithm checks every possible three digit even number exactly once. A number is included only if the input provides enough copies of every required digit. Since every valid number must be a three digit even number, and every such candidate is tested, the algorithm guarantees that all valid answers are included and no invalid answers appear in the result.
Python Solution
from typing import List
class Solution:
def findEvenNumbers(self, digits: List[int]) -> List[int]:
digit_count = [0] * 10
for digit in digits:
digit_count[digit] += 1
result = []
for num in range(100, 1000, 2):
hundreds = num // 100
tens = (num // 10) % 10
ones = num % 10
needed = [0] * 10
needed[hundreds] += 1
needed[tens] += 1
needed[ones] += 1
valid = True
for digit in range(10):
if needed[digit] > digit_count[digit]:
valid = False
break
if valid:
result.append(num)
return result
The implementation begins by constructing a frequency array named digit_count. This array records how many times each digit appears in the input.
Next, the algorithm iterates through all three digit even numbers using:
for num in range(100, 1000, 2):
Stepping by 2 guarantees that every candidate number is even.
For each candidate number, the code extracts the hundreds, tens, and ones digits using integer arithmetic. A second frequency array named needed tracks how many times each digit is required to form the current number.
The algorithm then compares needed against digit_count. If any digit is required more times than available, the candidate is rejected.
Otherwise, the number is appended to the result list.
Because numbers are checked in ascending order, the final list is automatically sorted.
Go Solution
func findEvenNumbers(digits []int) []int {
digitCount := make([]int, 10)
for _, digit := range digits {
digitCount[digit]++
}
result := []int{}
for num := 100; num < 1000; num += 2 {
hundreds := num / 100
tens := (num / 10) % 10
ones := num % 10
needed := make([]int, 10)
needed[hundreds]++
needed[tens]++
needed[ones]++
valid := true
for digit := 0; digit < 10; digit++ {
if needed[digit] > digitCount[digit] {
valid = false
break
}
}
if valid {
result = append(result, num)
}
}
return result
}
The Go implementation follows the same logic as the Python version.
Slices are used instead of Python lists for the frequency arrays. The result slice is dynamically expanded using append.
Go does not require special handling for integer overflow here because all values remain well within the standard integer range.
An empty result slice is returned naturally if no valid numbers exist.
Worked Examples
Example 1
Input:
digits = [2,1,3,0]
Step 1: Build Frequency Array
| Digit | Count |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
Step 2: Check Candidate Numbers
| Candidate | Even? | Leading Zero? | Valid Frequencies? | Result |
|---|---|---|---|---|
| 100 | Yes | No | Needs two 0s, invalid | Reject |
| 102 | Yes | No | Available | Accept |
| 104 | Yes | No | No 4 present | Reject |
| 120 | Yes | No | Available | Accept |
| 130 | Yes | No | Available | Accept |
| 132 | Yes | No | Available | Accept |
The process continues until 998.
Final output:
[102,120,130,132,210,230,302,310,312,320]
Example 2
Input:
digits = [2,2,8,8,2]
Frequency Table
| Digit | Count |
|---|---|
| 2 | 3 |
| 8 | 2 |
Candidate Checks
| Candidate | Required Digits | Valid? |
|---|---|---|
| 222 | three 2s | Yes |
| 228 | two 2s, one 8 | Yes |
| 282 | two 2s, one 8 | Yes |
| 288 | one 2, two 8s | Yes |
| 822 | one 8, two 2s | Yes |
| 828 | two 8s, one 2 | Yes |
| 882 | two 8s, one 2 | Yes |
Final output:
[222,228,282,288,822,828,882]
Example 3
Input:
digits = [3,7,5]
Frequency Table
| Digit | Count |
|---|---|
| 3 | 1 |
| 5 | 1 |
| 7 | 1 |
Every three digit number formed from these digits ends with an odd digit, so no valid even numbers exist.
Final output:
[]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n + 900) | Counting digits takes O(n), checking all three digit even numbers takes constant work |
| Space | O(1) | Frequency arrays have fixed size 10 |
The algorithm is effectively constant time with respect to the problem constraints because there are only 450 candidate even numbers between 100 and 999.
The auxiliary memory usage is also constant because both frequency arrays always contain exactly 10 entries.
Test Cases
from typing import List
class Solution:
def findEvenNumbers(self, digits: List[int]) -> List[int]:
digit_count = [0] * 10
for digit in digits:
digit_count[digit] += 1
result = []
for num in range(100, 1000, 2):
hundreds = num // 100
tens = (num // 10) % 10
ones = num % 10
needed = [0] * 10
needed[hundreds] += 1
needed[tens] += 1
needed[ones] += 1
valid = True
for digit in range(10):
if needed[digit] > digit_count[digit]:
valid = False
break
if valid:
result.append(num)
return result
solution = Solution()
assert solution.findEvenNumbers([2,1,3,0]) == [
102,120,130,132,210,230,302,310,312,320
] # standard mixed digits example
assert solution.findEvenNumbers([2,2,8,8,2]) == [
222,228,282,288,822,828,882
] # repeated digits example
assert solution.findEvenNumbers([3,7,5]) == [] # no even digits available
assert solution.findEvenNumbers([0,0,0]) == [] # leading zeros prevent valid numbers
assert solution.findEvenNumbers([1,1,1,2]) == [
112
] # requires repeated digit usage
assert solution.findEvenNumbers([8,8,8]) == [
888
] # all digits identical
assert solution.findEvenNumbers([0,2,2]) == [
202,220
] # zeros allowed internally but not leading
assert solution.findEvenNumbers([4,4,4,4]) == [
444
] # duplicate-heavy input
assert solution.findEvenNumbers([1,2,3,4,5,6]) == [
124,126,132,134,136,142,146,152,154,156,
162,164,214,216,234,236,246,254,256,264,
312,314,316,324,326,342,346,352,354,356,
362,364,412,416,432,436,452,456,462,512,
514,516,524,526,532,534,536,542,546,562,
564,612,614,632,634,642,652,654
] # larger mixed input
Test Summary
| Test | Why |
|---|---|
[2,1,3,0] |
Standard example with zeros and mixed digits |
[2,2,8,8,2] |
Validates duplicate digit handling |
[3,7,5] |
Ensures no odd-only solutions are returned |
[0,0,0] |
Verifies leading zero rejection |
[1,1,1,2] |
Tests repeated digit frequency counting |
[8,8,8] |
Tests identical digits forming one valid number |
[0,2,2] |
Ensures zero is allowed internally |
[4,4,4,4] |
Heavy duplication edge case |
[1,2,3,4,5,6] |
Stress test with many valid outputs |
Edge Cases
Inputs Containing Only Odd Digits
An input like [3,5,7] cannot form any even number because the last digit of every generated number would also be odd.
A buggy implementation might still produce outputs if it forgets to enforce the even number requirement. This implementation avoids that issue by iterating only through even candidate numbers.
Leading Zero Situations
An input such as [0,1,2] can form 102 and 120, but cannot form 012.
This is a common source of mistakes when generating permutations directly. The implementation handles this automatically because it only checks numbers from 100 to 999, meaning every candidate already has a valid hundreds digit.
Repeated Digit Requirements
An input like [2,8,8] should allow 288 but not 888.
The challenge is ensuring that digits are not reused more times than available. The frequency comparison guarantees correctness because each candidate number must satisfy:
needed[digit] <= available[digit]
for every digit from 0 to 9.
Duplicate Numbers from Different Index Choices
With input [2,2,8], different index combinations can produce the same number such as 228.
A brute force permutation approach may accidentally add duplicates multiple times. The optimal solution avoids this issue entirely because each candidate number is checked only once.