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] <= 9Problem 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.
This approach involves two steps:
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.
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.
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.
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.
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.
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.
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.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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. |
Leetcode 2605: Form Smallest Number From Two Digit Arrays • Algorithms Casts • 497 views views
Watch 9 more video solutions →Practice Form Smallest Number From Two Digit Arrays with our built-in code editor and test cases.
Practice on FleetCode