Form Smallest Number From Two Digit Arrays - Solution & Explanation
Problem Statement
nums1 and nums2, return the smallest number that contains at least one digit from each array.
Example 1:
Input: nums1 = [4,1,3], nums2 = [5,7] Output: 15 Explanation: The number 15 contains the digit 1 from nums1 and the digit 5 from nums2. It can be proven that 15 is the smallest number we can have.
Example 2:
Input: nums1 = [3,5,2,6], nums2 = [3,1,7] Output: 3 Explanation: The number 3 contains the digit 3 which exists in both arrays.
Constraints:
1 <= nums1.length, nums2.length <= 91 <= nums1[i], nums2[i] <= 9- All digits in each array are unique.
Approach Overview
Problem Overview: You are given two arrays containing digits (1–9). The task is to form the smallest possible integer using digits from both arrays. If the arrays share a common digit, that digit alone forms the smallest number. Otherwise, combine the smallest digits from each array to create the smallest two-digit number.
Approach 1: Intersection and Small Pair Approach (O(n + m) time, O(1) space)
The key observation: a single-digit number is always smaller than any two-digit number. If both arrays share a common digit, that digit is automatically the smallest valid result. Use a small boolean frequency array or a hash set to record digits from the first array, then iterate through the second array to detect intersections. Track the smallest shared digit while scanning.
If no intersection exists, compute the smallest digit from each array and form two candidate numbers: a*10 + b and b*10 + a. Choose the smaller one. This method performs simple iterations and constant-time lookups using a hash table style structure. Because digits range only from 1–9, the space remains constant. The algorithm runs in linear time relative to input size and is the optimal solution.
Approach 2: Brute Force Construction (O(n × m) time, O(1) space)
The brute force approach checks every pair of digits between the two arrays. For each pair (a, b), construct both possible two-digit numbers (a*10 + b and b*10 + a) and track the smallest result. Additionally, check if a == b; if so, that digit alone can form a single-digit candidate.
This solution relies on straightforward enumeration of all possible combinations. It guarantees correctness but does unnecessary work when the arrays are large. Time complexity grows with the product of both array sizes, making it less efficient than the intersection-based strategy.
Both approaches rely on basic iteration over an array. The difference lies in how efficiently they detect shared digits and build the minimal result.
Recommended for interviews: The Intersection and Small Pair approach is what interviewers expect. It shows you recognize that a shared digit immediately produces the smallest number and that hash lookups reduce unnecessary pair checks. The brute force version is still useful as a starting point during interviews to demonstrate baseline reasoning before optimizing.
Approach 1: Intersection and Small Pair Approach
This approach involves two steps:
- Check for common elements between the two arrays. If a common element exists, that digit itself is the smallest number possible.
- If there is no common digit, form the smallest two-digit number by selecting the smallest digit from each array.
The C solution initializes an array to track common elements. It iterates over both input arrays, recording any minimum values and checking for common digits. If a common digit is found, it's immediately returned as the solution. If not, the smallest possible two-digit number is formed from the minimal values in each array.
Complexity
Time Complexity: O(n + m) where n and m are the lengths of nums1 and nums2 respectively.
Space Complexity: O(1) due to the fixed size of the common tracking array.
Approach 2: Brute Force Construction
This approach simply tries all combinations by looping through both arrays to find a suitable number containing elements from each, though it's less efficient than the intersection approach.
This C solution checks all possible combinations of numbers formed by digits from nums1 and nums2. It attempts to construct both possible two-digit numbers from each pair of digits, storing the smallest result found.
Complexity
Time Complexity: O(n * m), where n and m are the sizes of nums1 and nums2.
Space Complexity: O(1), with no additional storage aside from variables.
Approach 3: Enumeration
We observe that if there are the same numbers in the arrays nums1 and nums2, then the minimum of the same numbers is the smallest number. Otherwise, we take the number a in the array nums1 and the number b in the array nums2, and concatenate the two numbers a and b into two numbers, and take the smaller number.
The time complexity is O(m times n), and the space complexity is O(1), where m and n are the lengths of the arrays nums1 and nums2.
Approach 4: Hash Table or Array + Enumeration
We can use a hash table or array to record the numbers in the arrays nums1 and nums2, and then enumerate 1 \sim 9. If i appears in both arrays, then i is the smallest number. Otherwise, we take the number a in the array nums1 and the number b in the array nums2, and concatenate the two numbers a and b into two numbers, and take the smaller number.
The time complexity is (m + n), and the space complexity is O(C). Where m and n are the lengths of the arrays nums1 and nums2 respectively; and C is the range of the numbers in the arrays nums1 and nums2, and the range in this problem is C = 10.
Approach 5: Bit Operation
Since the range of the numbers is 1 \sim 9, we can use a binary number with a length of 10 to represent the numbers in the arrays nums1 and nums2. We use mask1 to represent the numbers in the array nums1, and use mask2 to represent the numbers in the array nums2.
If the number mask obtained by performing a bitwise AND operation on mask1 and mask2 is not equal to 0, then we extract the position of the last 1 in the number mask, which is the smallest number.
Otherwise, we extract the position of the last 1 in mask1 and mask2 respectively, and denote them as a and b, respectively. Then the smallest number is min(a times 10 + b, b times 10 + a).
The time complexity is O(m + n), and the space complexity is O(1). Where m and n are the lengths of the arrays nums1 and nums2 respectively.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Intersection and Small Pair Approach | Time Complexity: O(n + m) where n and m are the lengths of nums1 and nums2 respectively. |
| Brute Force Construction | Time Complexity: O(n * m), where n and m are the sizes of nums1 and nums2. |
| Enumeration | — |
| Hash Table or Array + Enumeration | — |
| Bit Operation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Intersection and Small Pair Approach | O(n + m) | O(1) | Best general solution. Quickly detects common digits and builds the minimal number efficiently. |
| Brute Force Construction | O(n × m) | O(1) | Useful for understanding the problem or when constraints are extremely small. |
Video Solution
Leetcode 2605: Form Smallest Number From Two Digit Arrays • Algorithms Casts • 509 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Form Smallest Number From Two Digit Arrays easy or hard?
Form Smallest Number From Two Digit Arrays Python/Java solution
How to solve Form Smallest Number From Two Digit Arrays in O(n)?
What is the best approach for Form Smallest Number From Two Digit Arrays?
Is Form Smallest Number From Two Digit Arrays asked at Google/Amazon/Meta?
What data structure is used in Form Smallest Number From Two Digit Arrays?
What is the time complexity of Form Smallest Number From Two Digit Arrays?
Ready to solve this problem?
Practice Form Smallest Number From Two Digit Arrays with our built-in code editor and test cases.
Practice on FleetCode