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.
This is a straightforward approach that directly translates the problem's conditions into code. It checks for common digits using nested loops and separately finds the minimums of each array to handle the case where no common digits exist.
Algorithm
- Initialize
minCommonto a value greater than any possible digit (e.g., 10). - Iterate through each digit
d1innums1. - Inside this loop, iterate through each digit
d2innums2. - If
d1is equal tod2, updateminCommon = min(minCommon, d1). - After the nested loops, check if
minCommonwas updated (i.e.,minCommon < 10). If so, a common digit was found, and the smallest one is the answer. ReturnminCommon. - If no common digit was found, find the minimum digit
min1innums1andmin2innums2by iterating through them separately. - The result is the smallest two-digit number that can be formed. Return
min(min1 * 10 + min2, min2 * 10 + min1).
Walkthrough
The smallest possible number can either be a single digit (if a digit exists in both arrays) or a two-digit number. A single-digit number is always smaller than any two-digit number. Therefore, the primary goal is to find if there's a common digit, and if so, which one is the smallest.
This brute-force algorithm proceeds as follows:
- First, it attempts to find the smallest common digit by comparing every digit from
nums1with every digit fromnums2. - It uses a variable,
minCommon, initialized to a value larger than any digit (like 10), to keep track of the smallest common digit found. - If a common digit is found,
minCommonwill hold the smallest such digit. Since this is a single-digit number, it must be the smallest possible number we can form. The algorithm returns this value. - If the loops complete and
minCommonhasn't changed, it means there are no common digits. In this scenario, the smallest number must be a two-digit number. - To form the smallest two-digit number, we must use the smallest possible digit for the tens place. This requires finding the minimum digit from
nums1(min1) and the minimum digit fromnums2(min2). - The two candidate numbers are
min1followed bymin2andmin2followed bymin1. The algorithm returns the smaller of these two.
class Solution { public int minNumber(int[] nums1, int[] nums2) { int minCommon = 10; for (int x : nums1) { for (int y : nums2) { if (x == y) { minCommon = Math.min(minCommon, x); } } } if (minCommon != 10) { return minCommon; } int min1 = 10; for (int x : nums1) { min1 = Math.min(min1, x); } int min2 = 10; for (int x : nums2) { min2 = Math.min(min2, x); } return Math.min(min1 * 10 + min2, min2 * 10 + min1); }}Complexity
Time
O(N * M), where N and M are the lengths of `nums1` and `nums2` respectively. The nested loops for finding the common digit dominate the runtime. The subsequent loops to find minimums take O(N + M), which is subsumed by O(N*M).
Space
O(1), as it only uses a constant amount of extra space for variables.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space besides a few variables.
Cons
The time complexity of O(N*M) is inefficient for larger inputs, although it passes given the problem's constraints.
This approach improves the search for a common digit by sorting the arrays first. This allows for a linear-time scan using two pointers to find the smallest common digit.
Algorithm
- Sort both
nums1andnums2in non-decreasing order. - Initialize two pointers,
ifornums1andjfornums2, both starting at 0. - Iterate while both pointers are within their respective array bounds:
- If
nums1[i] == nums2[j], a common digit is found. Since the arrays are sorted, this is the smallest common digit. Return it. - If
nums1[i] < nums2[j], incrementito find a potentially larger matching digit innums1. - Else (
nums1[i] > nums2[j]), incrementj.
- If
- If the loop finishes without returning, no common digits exist.
- The smallest digit in
nums1isnums1[0]and innums2isnums2[0]. Return the smaller of the two-digit numbers formed by them:min(nums1[0] * 10 + nums2[0], nums2[0] * 10 + nums1[0]).
Walkthrough
By sorting the arrays, we can find both the minimum elements and the common elements more efficiently than a brute-force search.
The algorithm is as follows:
- Sort both
nums1andnums2in ascending order. This brings the smallest elements to the front and groups identical elements (if any) together, making comparisons efficient. - To find the smallest common digit, use a two-pointer technique. One pointer
itraversesnums1, and another pointerjtraversesnums2. - Compare the elements at the current pointers. If
nums1[i]andnums2[j]are equal, we've found a common digit. Because the arrays are sorted, this must be the smallest common digit, so we can return it immediately. - If the elements are not equal, we advance the pointer pointing to the smaller element, as that smaller element cannot be a common digit with the current larger element.
- If the two-pointer scan completes without finding any common elements, we proceed to form a two-digit number. Since the arrays are sorted, the smallest element of
nums1isnums1[0]and the smallest ofnums2isnums2[0]. The result is the minimum of the two numbers formed by concatenating these digits.
import java.util.Arrays; class Solution { public int minNumber(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int i = 0, j = 0; while (i < nums1.length && j < nums2.length) { if (nums1[i] == nums2[j]) { return nums1[i]; // Smallest common digit found } else if (nums1[i] < nums2[j]) { i++; } else { j++; } } // No common digit found int min1 = nums1[0]; int min2 = nums2[0]; return Math.min(min1 * 10 + min2, min2 * 10 + min1); }}Complexity
Time
O(N log N + M log M), where N and M are the array lengths. Sorting is the most time-consuming part. The subsequent two-pointer scan takes O(N + M), which is dominated by the sorting time.
Space
O(log N + log M) to O(N + M), depending on the space used by the sorting algorithm. For instance, Java's `Arrays.sort` for primitives has an average space complexity of O(log N).
Trade-offs
Pros
More efficient than the brute-force approach for larger arrays.
The logic is clean and leverages a standard algorithm (two pointers on sorted arrays).
Cons
The time complexity is dominated by sorting, which may not be the most optimal for this problem.
Sorting modifies the input arrays or requires extra space, depending on the implementation.
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; }}class Solution {public: int minNumber(vector<int> &nums1, vector<int> &nums2) { int ans = 100; for (int a : nums1) { for (int b : nums2) { if (a == b) { ans = min(ans, a); } else { ans = min({ans, a * 10 + b, b * 10 + a}); } } } return ans; }};class Solution: def minNumber(self, nums1: List[int], nums2: List[int]) -> int: ans = 100 for a in nums1: for b in nums2: if a == b: ans = min(ans, a) else: ans = min(ans, 10 * a + b, 10 * b + a) return ansVideo 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.