Finding 3-Digit Even Numbers - Video Solutions
Finding 3-Digit Even Numbers | 2 Simple Approaches | Leetcode 2094 | codestorywithMIK
Finding 3-Digit Even Numbers - Video Solution
Watch 10 video solutions for Finding 3-Digit Even Numbers, a easy level problem involving Array, Hash Table, Sorting. This walkthrough by codestorywithMIK has 10,467 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an integer array digits, where each element is a digit. The array may contain duplicates.
You need to find all the unique integers that follow the given requirements:
- The integer consists of the concatenation of three elements from
digitsin any arbitrary order. - The integer does not have leading zeros.
- The integer is even.
For example, if the given digits were [1, 2, 3], integers 132 and 312 follow the requirements.
Return a sorted array of the unique integers.
Example 1:
Input: digits = [2,1,3,0] Output: [102,120,130,132,210,230,302,310,312,320] Explanation: All the possible integers that follow the requirements are in the output array. Notice that there are no odd integers or integers with leading zeros.
Example 2:
Input: digits = [2,2,8,8,2] Output: [222,228,282,288,822,828,882] Explanation: The same digit can be used as many times as it appears in digits. In this example, the digit 8 is used twice each time in 288, 828, and 882.
Example 3:
Input: digits = [3,7,5] Output: [] Explanation: No even integers can be formed using the given digits.
Constraints:
3 <= digits.length <= 1000 <= digits[i] <= 9
Approach Overview
Problem Overview: You receive an array of digits (0–9). Use these digits to construct all unique 3-digit even numbers. Each digit can only be used as many times as it appears in the array. The result must contain every valid number exactly once and be returned in sorted order.
Approach 1: Using a Hash Map (Digit Frequency) (Time: O(450 * 10) ≈ O(1), Space: O(10))
Create a frequency map of digits using a small array or hash table. Then enumerate every possible 3-digit even number from 100 to 998. For each candidate number, extract the hundreds, tens, and units digits. The key check: verify the units digit is even and ensure the digit frequency in the candidate does not exceed the available frequency in the input map. This works because there are only 450 possible 3-digit even numbers, so enumeration is effectively constant time. The approach relies on fast frequency comparison rather than generating permutations, which avoids duplicate work.
Use this method when the domain of valid numbers is small and bounded. Instead of exploring combinations from the array, you validate candidates against available digits. This pattern appears frequently in hash table and array counting problems.
Approach 2: Sorting and Linear Enumeration (Time: O(n^3), Space: O(1) extra)
Sort the digits first. Then iterate over all triples of indices i, j, and k to form numbers using three distinct positions. Skip invalid combinations early: the first digit cannot be 0, and the last digit must be even. Sorting allows easy duplicate control because identical digits appear next to each other, so you can skip repeated combinations during iteration. Construct the number as 100*a + 10*b + c and store unique results.
This approach directly generates candidate numbers from the input digits rather than validating against a fixed range. Sorting simplifies duplicate handling and is a common pattern in sorting-based enumeration problems. It is slightly slower asymptotically but still efficient since the input size is small (digits length ≤ 10).
Recommended for interviews: The hash map enumeration approach is usually preferred. It demonstrates awareness of constraints and converts the problem into constant-size validation rather than combinatorial generation. Interviewers appreciate recognizing the small search space (only 3-digit even numbers). The sorting + enumeration method still shows solid reasoning about duplicates and index usage, so it remains a good fallback when the range-based insight does not immediately come to mind.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Frequency + Enumerate 3-digit Even Numbers | O(450 * 10) ≈ O(1) | O(10) | Best when the possible result range is small and fixed |
| Sorting + Triple Enumeration | O(n^3) | O(1) | Useful when generating combinations directly from digits |