Problem Description

You are given two arrays nums1 and nums2, where each array contains unique digits (0-9). Your task is to find the smallest possible number that contains at least one digit from nums1 and at least one digit from nums2.

The number you form must include:

• At least one digit that appears in nums1
• At least one digit that appears in nums2

These conditions can be satisfied by:

1. A single digit that appears in both arrays, or
2. A two-digit number formed by taking one digit from each array

For example:

• If nums1 = [4, 1, 3] and nums2 = [5, 7], the smallest number would be 15 (using 1 from nums1 and 5 from nums2)
• If nums1 = [3, 5, 2] and nums2 = [3, 4, 6], the smallest number would be 3 (since 3 appears in both arrays)

The goal is to return the minimum such number that satisfies the requirement of containing at least one digit from each array.

Intuition

When we need to form the smallest number containing digits from both arrays, we should think about what the possible cases are:

1. Common digit exists: If both arrays share a common digit, then that single digit satisfies the requirement of "containing at least one digit from each array". Among all common digits, we'd want the smallest one.

2. No common digit: If there's no overlap between the arrays, we must form a two-digit number by taking one digit from each array. To make the smallest two-digit number, we should place the smaller digit in the tens place and the larger digit in the ones place.

Since we want the absolute minimum, we need to check all possibilities:

• Every pair of digits (a, b) where a is from nums1 and b is from nums2
• If a == b, this gives us a single-digit option: just a
• If a != b, we have two possible two-digit numbers: 10 * a + b and 10 * b + a. We need to consider both because we don't know which arrangement is smaller without comparing.

By examining all pairs and keeping track of the minimum value found, we ensure we get the smallest possible number. The enumeration approach works well here because the arrays contain at most 10 unique digits each (0-9), making the total number of pairs to check at most 100, which is very manageable.

Solution Approach

The solution uses a brute force enumeration approach to check all possible combinations:

1. Initialize the answer: Start with ans = 100 as an upper bound (since the maximum two-digit number we can form with digits 0-9 would be 98).

2. Nested loops for all pairs: Iterate through every digit a from nums1 and every digit b from nums2 to examine all possible pairs.

3. Check each pair:

   • If a == b (common digit found): Update ans with min(ans, a). This single digit satisfies both requirements.
   • If a != b (different digits): We can form two possible two-digit numbers:
     • 10 * a + b: Places a in tens position, b in ones position
     • 10 * b + a: Places b in tens position, a in ones position
     • Update ans with the minimum of these three values: min(ans, 10 * a + b, 10 * b + a)

4. Return the result: After checking all pairs, ans contains the smallest possible number.

The algorithm has a time complexity of O(m * n) where m and n are the lengths of nums1 and nums2 respectively. Since each array contains at most 10 unique digits, this is effectively O(1) constant time.

The space complexity is O(1) as we only use a single variable to track the minimum value.

Example Walkthrough

Let's walk through the solution with nums1 = [4, 1, 3] and nums2 = [5, 7].

Step 1: Initialize

• Set ans = 100 (our upper bound)

Step 2: Check all pairs

For a = 4 from nums1:

• Pair (4, 5): Since 4 ≠ 5, we can form:
  • 10 * 4 + 5 = 45
  • 10 * 5 + 4 = 54
  • Update: ans = min(100, 45, 54) = 45
• Pair (4, 7): Since 4 ≠ 7, we can form:
  • 10 * 4 + 7 = 47
  • 10 * 7 + 4 = 74
  • Update: ans = min(45, 47, 74) = 45

For a = 1 from nums1:

• Pair (1, 5): Since 1 ≠ 5, we can form:
  • 10 * 1 + 5 = 15
  • 10 * 5 + 1 = 51
  • Update: ans = min(45, 15, 51) = 15
• Pair (1, 7): Since 1 ≠ 7, we can form:
  • 10 * 1 + 7 = 17
  • 10 * 7 + 1 = 71
  • Update: ans = min(15, 17, 71) = 15

For a = 3 from nums1:

• Pair (3, 5): Since 3 ≠ 5, we can form:
  • 10 * 3 + 5 = 35
  • 10 * 5 + 3 = 53
  • Update: ans = min(15, 35, 53) = 15
• Pair (3, 7): Since 3 ≠ 7, we can form:
  • 10 * 3 + 7 = 37
  • 10 * 7 + 3 = 73
  • Update: ans = min(15, 37, 73) = 15

Step 3: Return result

• The minimum value found is 15, which uses digit 1 from nums1 and digit 5 from nums2.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the length of nums1 and n is the length of nums2. This is because we have two nested loops - the outer loop iterates through all elements in nums1 (m iterations), and for each element, the inner loop iterates through all elements in nums2 (n iterations), resulting in a total of m × n operations.

The space complexity is O(1) as the algorithm only uses a constant amount of extra space. The only additional variable used is ans which stores a single integer value, regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Overlooking Leading Zeros in Two-Digit Numbers

A critical issue that developers often miss is the handling of the digit 0. When forming two-digit numbers, if one of the digits is 0, placing it in the tens position would create an invalid two-digit number.

Example of the problem:

• If nums1 = [0, 2] and nums2 = [3]
• The code would consider 10 * 0 + 3 = 3 and 10 * 3 + 0 = 30
• While 3 is correct, this happens by coincidence rather than proper logic
• If nums1 = [0] and nums2 = [5], the code would form 10 * 0 + 5 = 5 and 10 * 5 + 0 = 50, returning 5 instead of the correct answer 50

Why this matters: The number 05 is not a valid two-digit number—it's actually the single-digit number 5. This violates the problem's requirement that we need at least one digit from each array. If 0 is from one array and 5 is from another, we cannot use just 5 as our answer unless 5 also appears in the first array.

Solution to the Pitfall:

class Solution:
    def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
        min_result = 100
      
        for digit1 in nums1:
            for digit2 in nums2:
                if digit1 == digit2:
                    # Common digit found
                    min_result = min(min_result, digit1)
                else:
                    # Form two-digit numbers, but avoid leading zeros
                    if digit1 != 0:  # digit1 can be in tens position
                        min_result = min(min_result, 10 * digit1 + digit2)
                    if digit2 != 0:  # digit2 can be in tens position
                        min_result = min(min_result, 10 * digit2 + digit1)
      
        return min_result

Alternative Approach: Another way to handle this is to check for common digits first, then find the minimum digits from each array:

class Solution:
    def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
        # Check for common digits first
        common = set(nums1) & set(nums2)
        if common:
            return min(common)
      
        # No common digits, form a two-digit number
        min1 = min(nums1)
        min2 = min(nums2)
      
        # Place the smaller non-zero digit first
        if min1 == 0:
            return 10 * min2  # min2 cannot be 0 since no common digits
        elif min2 == 0:
            return 10 * min1
        else:
            return 10 * min(min1, min2) + max(min1, min2)

This approach is cleaner and avoids the leading zero issue by explicitly handling the logic of number formation.