Form Smallest Number From Two Digit Arrays

Difficulty: Easy | Acceptance: 55.20% | Paid: No Topics: Array, Hash Table, Enumeration

Given two arrays of integers nums1 and nums2, return the smallest number that contains at least one digit from each array.

You are given two integer arrays nums1 and nums2 consisting of digits (0-9). You need to form a number by selecting digits from these arrays. The number must contain at least one digit from nums1 and at least one digit from nums2.

Return the smallest such number. If there are multiple answers, return the smallest one. If no such number exists, return -1.

• Examples
• Constraints
• Approach 1: Hash Set
• Approach 2: Sorting
• Approach 3: Brute Force

Examples

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 <= 9
1 <= nums1[i], nums2[i] <= 9
All digits in each array are unique.

Approach 1: Hash Set

Intuition The smallest possible number is a single digit if there is a common digit between the two arrays. If no common digit exists, the smallest number must be a two-digit number formed by the smallest digit from each array.

Steps

• Convert nums1 into a hash set for O(1) lookups.
• Iterate through nums2 to find the smallest digit that exists in the set of nums1.
• If a common digit is found, return it immediately as it is the smallest possible answer.
• If no common digit is found, find the minimum digit in nums1 (min1) and the minimum digit in nums2 (min2).
• Return the smaller of the two possible two-digit numbers: min1 * 10 + min2 or min2 * 10 + min1.

class Solution:
    def minNumber(self, nums1: list[int], nums2: list[int]) -> int:
        set1 = set(nums1)
        min_common = float('inf')
        
        for x in nums2:
            if x in set1:
                if x < min_common:
                    min_common = x
        
        if min_common != float('inf'):
            return min_common
        
        min1 = min(nums1)
        min2 = min(nums2)
        
        return min(min1 * 10 + min2, min2 * 10 + min1)

Complexity

• Time: O(n + m), where n and m are the lengths of the arrays.
• Space: O(n) to store the hash set.
• Notes: This is the most optimal approach for time complexity.

Approach 2: Sorting

Intuition Sorting both arrays allows us to easily find the smallest digits and check for common digits using a two-pointer technique.

Steps

• Sort both nums1 and nums2 in ascending order.
• Use two pointers to iterate through both arrays simultaneously to find the first common digit.
• If a common digit is found, return it.
• If no common digit is found, the smallest digits are at index 0 of both arrays.
• Construct the two possible two-digit numbers and return the smaller one.

class Solution:
    def minNumber(self, nums1: list[int], nums2: list[int]) -> int:
        nums1.sort()
        nums2.sort()
        
        i, j = 0, 0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                return nums1[i]
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        
        min1, min2 = nums1[0], nums2[0]
        return min(min1 * 10 + min2, min2 * 10 + min1)

Complexity

• Time: O(n log n + m log m) due to sorting.
• Space: O(1) or O(log n) depending on the sorting algorithm’s stack space.
• Notes: Sorting is slightly slower than the hash set approach but avoids extra space for the set.

Approach 3: Brute Force

Intuition Since the constraints are very small (arrays of length at most 9), we can simply check every possible pair of digits to find commonalities and minimums.

Steps

• Initialize min_common to a value larger than 9 (e.g., 10).
• Initialize min1 and min2 to 10.
• Iterate through every digit a in nums1 and every digit b in nums2.
• Update min1 and min2 with the minimum values found so far.
• If a == b, update min_common with the minimum of itself and a.
• If min_common is less than 10, return min_common.
• Otherwise, return the smaller of the two combinations of min1 and min2.

class Solution:
    def minNumber(self, nums1: list[int], nums2: list[int]) -> int:
        min_common = 10
        min1 = 10
        min2 = 10
        
        for a in nums1:
            if a < min1:
                min1 = a
            for b in nums2:
                if b < min2:
                    min2 = b
                if a == b and a < min_common:
                    min_common = a
        
        if min_common < 10:
            return min_common
        
        return min(min1 * 10 + min2, min2 * 10 + min1)

Complexity

• Time: O(n * m), where n and m are the lengths of the arrays.
• Space: O(1).
• Notes: This approach is simple and acceptable given the small constraints, but less efficient than the hash set approach for larger inputs.