Form Smallest Number From Two Digit Arrays
EasyPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most efficient approach, achieving linear time complexity. It uses a frequency array (or a hash set) to keep track of digits from one array and then iterates through the second array to find common digits and minimums in just two passes.
Algorithm
- Initialize
min1 = 10and a boolean arrayseenof size 10 to allfalse. - Iterate through
nums1. For each digitd, updatemin1 = min(min1, d)and setseen[d] = true. - Initialize
min2 = 10andminCommon = 10. - Iterate through
nums2. For each digitd, updatemin2 = min(min2, d). Also, check ifseen[d]is true. If it is, updateminCommon = min(minCommon, d). - After both loops, if
minCommonis not 10, it holds the smallest common digit. ReturnminCommon. - Otherwise, no common digits exist. Return the smallest two-digit number formed from the minimums:
min(min1 * 10 + min2, min2 * 10 + min1).
Walkthrough
This method avoids both nested loops and sorting by using an auxiliary data structure to store information about the digits. Since the digits are constrained to be between 1 and 9, a simple boolean array of size 10 serves as a highly efficient hash set.
The algorithm combines finding the minimums and the common digits into two separate linear passes:
- Process
nums1: Iterate throughnums1once. During this pass, do two things: find the minimum digit innums1(min1) and mark the presence of each digit in theseenboolean array. - Process
nums2: Iterate throughnums2once. During this pass, do two things: find the minimum digit innums2(min2) and check for common digits. A digitdfromnums2is common ifseen[d]is true. Keep track of the smallest common digit found in a variableminCommon. - Determine Result: After the two passes, if
minCommonhas been updated, it holds the smallest common digit, which is the answer. If not, no common digits exist, and the answer is the smallest two-digit number formed bymin1andmin2.
This approach is optimal because it processes each element in the input arrays a constant number of times.
class Solution { public int minNumber(int[] nums1, int[] nums2) { int min1 = 10; boolean[] seen = new boolean[10]; for (int x : nums1) { min1 = Math.min(min1, x); seen[x] = true; } int min2 = 10; int minCommon = 10; for (int x : nums2) { min2 = Math.min(min2, x); if (seen[x]) { minCommon = Math.min(minCommon, x); } } if (minCommon != 10) { return minCommon; } return Math.min(min1 * 10 + min2, min2 * 10 + min1); }}Complexity
Time
O(N + M), where N and M are the lengths of the arrays. We iterate through each array exactly once.
Space
O(1), as the `seen` array has a fixed size of 10, which is constant and does not depend on the input array sizes.
Trade-offs
Pros
Optimal time complexity of O(N+M).
Uses constant extra space because the range of digits is fixed and small.
Cons
Slightly more complex than the brute-force approach due to the use of an auxiliary data structure.
Solutions
Solution
class Solution {public int minNumber(int[] nums1, int[] nums2) { int ans = 100; for (int a : nums1) { for (int b : nums2) { if (a == b) { ans = Math.min(ans, a); } else { ans = Math.min(ans, Math.min(a * 10 + b, b * 10 + a)); } } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.