LeetCode 2605 - Form Smallest Number From Two Digit Arrays
The problem gives us two arrays, nums1 and nums2, where each array contains unique digits from 1 to 9. We need to construct the smallest possible number such that the number contains at least one digit from each array.
Difficulty: 🟢 Easy
Topics: Array, Hash Table, Enumeration
Solution
Problem Understanding
The problem gives us two arrays, nums1 and nums2, where each array contains unique digits from 1 to 9. We need to construct the smallest possible number such that the number contains at least one digit from each array.
The phrase "contains at least one digit from each array" is the key requirement. A valid answer can be either:
- A single digit, if that digit exists in both arrays.
- A two digit number, if there is no common digit.
If a digit appears in both arrays, that digit alone already satisfies the condition because it belongs to both arrays simultaneously. Since any one digit number is always smaller than any two digit number, the smallest common digit immediately becomes the optimal answer.
If there is no common digit, then we must build a two digit number using one digit from nums1 and one digit from nums2. To minimize the number, we want:
- The smallest possible tens digit.
- Then the smallest possible ones digit.
For example:
nums1 = [4,1,3]nums2 = [5,7]
There is no common digit. The smallest digit in nums1 is 1, and the smallest digit in nums2 is 5. The two possible orderings are:
1551
Clearly, 15 is smaller.
The constraints are very small:
- Each array length is at most
9 - Digits range from
1to9 - Digits inside each array are unique
These constraints tell us that even inefficient approaches would work comfortably. However, the goal is still to design a clean and logically optimal solution.
There are several important edge cases:
- The arrays may already share a digit.
- The smallest common digit may not be the first element in either array.
- The arrays may have completely disjoint digits.
- The smallest valid two digit number may require reversing the order of the chosen digits.
The problem guarantees:
- Every value is a valid digit from
1to9 - Arrays are non-empty
- Digits within the same array are unique
Because of these guarantees, we do not need to handle duplicates or empty input arrays.
Approaches
Brute Force Approach
A brute force solution tries every possible valid number.
First, we can check all single digit possibilities from 1 through 9 to see whether the digit appears in both arrays. If one exists, we return the smallest such digit.
If no common digit exists, we generate every possible two digit number using:
- One digit from
nums1 - One digit from
nums2
For every pair (a, b), we form:
10 * a + b10 * b + a
We then keep track of the minimum valid number.
This approach works because it explicitly checks every candidate answer. Since the input size is tiny, the total number of combinations is very small.
However, the brute force approach performs unnecessary work because we do not actually need to generate all combinations once we recognize the mathematical structure of the problem.
Optimal Approach
The key insight is that a one digit answer is always better than a two digit answer.
Therefore:
- First, search for a common digit between the arrays.
- If one exists, return the smallest common digit immediately.
- Otherwise, take the smallest digit from each array and combine them in the smaller possible order.
Suppose:
min1 = min(nums1)min2 = min(nums2)
The answer must be:
min(min1 * 10 + min2, min2 * 10 + min1)
This works because:
- Any larger digit in the tens place would produce a larger number.
- Any larger digit in the ones place would also increase the value.
The constraints are tiny, so using a hash set for quick membership checks makes the implementation straightforward and efficient.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n × m) | O(1) | Generates all possible combinations |
| Optimal | O(n + m) | O(n) | Uses a set to detect common digits efficiently |
Algorithm Walkthrough
- Convert
nums1into a hash set.
We use a set because membership checks are very fast. This allows us to quickly determine whether a digit from nums2 also exists in nums1.
2. Search for common digits.
Iterate through every digit in nums2. If the digit exists in the set created from nums1, then it is a common digit shared by both arrays.
3. Track the smallest common digit.
Since multiple common digits may exist, we keep the minimum one. A single digit number is always smaller than any two digit number, so if we find any common digit, the smallest one is automatically the final answer. 4. If a common digit exists, return it immediately.
At this point, we already know no two digit number can beat a one digit number. 5. Otherwise, compute the smallest digit in each array.
Let:
smallest1 = min(nums1)smallest2 = min(nums2)
- Form the two possible two digit numbers.
The valid numbers are:
smallest1 * 10 + smallest2smallest2 * 10 + smallest1
- Return the smaller of the two.
This guarantees the minimum possible two digit answer.
Why it works
The algorithm relies on a simple ordering property of numbers:
- Every one digit number is smaller than every two digit number.
- Therefore, if a common digit exists, the smallest common digit must be optimal.
- If no common digit exists, the smallest two digit number must use the smallest available digits from both arrays, arranged in the smaller order.
Because the algorithm exhausts all mathematically optimal possibilities, it always produces the correct minimum number.
Python Solution
from typing import List
class Solution:
def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
nums1_set = set(nums1)
smallest_common = 10
for digit in nums2:
if digit in nums1_set:
smallest_common = min(smallest_common, digit)
if smallest_common != 10:
return smallest_common
smallest1 = min(nums1)
smallest2 = min(nums2)
return min(
smallest1 * 10 + smallest2,
smallest2 * 10 + smallest1
)
The implementation starts by converting nums1 into a set so membership checks become efficient.
The variable smallest_common is initialized to 10, which is larger than any valid digit. While iterating through nums2, the code checks whether each digit also exists in nums1_set. If so, the algorithm updates the smallest common digit found so far.
After the loop:
- If a common digit was discovered, the algorithm returns it immediately.
- Otherwise, it computes the smallest digit in each array.
Finally, the code forms both possible two digit numbers and returns the smaller one.
The implementation directly follows the logical structure established in the algorithm walkthrough.
Go Solution
func minNumber(nums1 []int, nums2 []int) int {
nums1Set := make(map[int]bool)
for _, digit := range nums1 {
nums1Set[digit] = true
}
smallestCommon := 10
for _, digit := range nums2 {
if nums1Set[digit] {
if digit < smallestCommon {
smallestCommon = digit
}
}
}
if smallestCommon != 10 {
return smallestCommon
}
smallest1 := nums1[0]
for _, digit := range nums1 {
if digit < smallest1 {
smallest1 = digit
}
}
smallest2 := nums2[0]
for _, digit := range nums2 {
if digit < smallest2 {
smallest2 = digit
}
}
option1 := smallest1*10 + smallest2
option2 := smallest2*10 + smallest1
if option1 < option2 {
return option1
}
return option2
}
The Go implementation follows the same logic as the Python version. Since Go does not have a built in set type, a map[int]bool is used to simulate a hash set.
The minimum values are computed manually with loops because Go does not provide a built in min function for slices.
There are no integer overflow concerns because all values are tiny two digit numbers.
Worked Examples
Example 1
nums1 = [4,1,3]
nums2 = [5,7]
Step 1: Build the set
| Operation | Result |
|---|---|
| Convert nums1 to set | {1, 3, 4} |
Step 2: Search for common digits
| Current Digit from nums2 | Exists in Set? | smallest_common |
|---|---|---|
| 5 | No | 10 |
| 7 | No | 10 |
No common digit exists.
Step 3: Find smallest digits
| Array | Smallest Digit |
|---|---|
| nums1 | 1 |
| nums2 | 5 |
Step 4: Form candidate numbers
| Candidate | Value |
|---|---|
| 1 followed by 5 | 15 |
| 5 followed by 1 | 51 |
The minimum is 15.
Final answer:
15
Example 2
nums1 = [3,5,2,6]
nums2 = [3,1,7]
Step 1: Build the set
| Operation | Result |
|---|---|
| Convert nums1 to set | {2, 3, 5, 6} |
Step 2: Search for common digits
| Current Digit from nums2 | Exists in Set? | smallest_common |
|---|---|---|
| 3 | Yes | 3 |
| 1 | No | 3 |
| 7 | No | 3 |
A common digit exists, and the smallest one is 3.
Since a one digit number is always optimal compared to any two digit number, we return immediately.
Final answer:
3
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n + m) | One pass to build the set and one pass to scan the second array |
| Space | O(n) | The hash set stores digits from nums1 |
The runtime is linear in the combined size of the two arrays. Since each array contains at most nine elements, the actual runtime is extremely small in practice.
The auxiliary space comes from the hash set used for membership testing. Because the digits are unique and limited to 1 through 9, the maximum space usage is also very small.
Test Cases
solution = Solution()
assert solution.minNumber([4, 1, 3], [5, 7]) == 15
# No common digit, smallest two-digit number
assert solution.minNumber([3, 5, 2, 6], [3, 1, 7]) == 3
# Common digit exists
assert solution.minNumber([9], [9]) == 9
# Single-element arrays with same digit
assert solution.minNumber([8], [2]) == 28
# Single-element arrays with no overlap
assert solution.minNumber([1, 2, 3], [4, 5, 6]) == 14
# Smallest digits must be combined
assert solution.minNumber([7, 8], [1, 7]) == 7
# Shared digit is not the smallest in first array
assert solution.minNumber([5, 6], [1, 2]) == 15
# Reverse ordering matters
assert solution.minNumber([2, 8], [3, 9]) == 23
# Smallest arrangement chosen correctly
assert solution.minNumber([1, 9], [1, 8]) == 1
# Common smallest digit
assert solution.minNumber([6, 4], [5, 2]) == 24
# Smaller tens digit determines result
| Test | Why |
|---|---|
[4,1,3] and [5,7] |
Validates no-overlap behavior |
[3,5,2,6] and [3,1,7] |
Validates common digit optimization |
[9] and [9] |
Tests smallest possible input size with overlap |
[8] and [2] |
Tests smallest possible input size without overlap |
[1,2,3] and [4,5,6] |
Ensures smallest digits are selected |
[7,8] and [1,7] |
Confirms shared digit takes priority |
[5,6] and [1,2] |
Verifies digit ordering logic |
[2,8] and [3,9] |
Confirms minimal two-digit construction |
[1,9] and [1,8] |
Tests shared minimum digit |
[6,4] and [5,2] |
Ensures tens place minimization |
Edge Cases
One important edge case occurs when the arrays share a digit. A naive implementation might still attempt to construct two digit numbers, but that would be incorrect because any single digit number is smaller than every two digit number. The implementation handles this by checking for common digits first and immediately returning the smallest one found.
Another edge case occurs when there is no overlap at all. In this situation, the algorithm must carefully construct the smallest possible two digit number. Simply concatenating the smallest digit from nums1 first is not always optimal. For example:
nums1 = [8]nums2 = [2]
The correct answer is 28, not 82. The implementation correctly evaluates both orderings and returns the smaller one.
A third edge case involves arrays of minimum size. Since both arrays may contain only one element, some implementations might incorrectly assume multiple candidates exist. The current solution works correctly even when each array contains exactly one digit because the logic does not rely on array length greater than one.
Another subtle edge case is when the common digit is not encountered first during iteration. For example:
nums1 = [5, 2, 8]nums2 = [9, 8, 2]
Both 8 and 2 are common digits, but the correct answer is 2. The implementation keeps track of the minimum common digit instead of returning the first one found, ensuring correctness.