#2605

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Form Smallest Number From Two Digit Arrays

Given two arrays of digits, find the smallest possible number formed by one digit from each array.

Problem Statement

Given two arrays of digits, nums1 and nums2, your task is to form the smallest number possible by selecting one digit from each array. Both arrays contain unique digits, and you must form the smallest possible number by picking one digit from each array, with the order of the digits being important.

You need to return the smallest number that can be created. If there is a common digit between the two arrays, that digit should be selected. If no common digit exists, the smallest possible number can be formed from the smallest digits in each array.

Examples

Example 1

Input: nums1 = [4,1,3], nums2 = [5,7]

Output: 15

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

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.

Solution Approach

Array Scanning

Scan through both arrays to find the smallest common digit. If no common digit exists, select the smallest element from both arrays and form a number.

Hash Table Lookup

Use a hash table to quickly find if a digit in one array exists in the other. This allows constant time lookups for efficiency.

Edge Case Handling

Handle cases where the arrays contain no common digits by selecting the smallest digits from each array and combining them.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n + m) where n and m are the lengths of nums1 and nums2, respectively, due to the scanning and lookup operations. The space complexity is O(n + m) for storing the hash table of digits.

What Interviewers Usually Probe

Tests the candidate's ability to efficiently scan and compare arrays.
Evaluates understanding of hash tables for fast lookups.
Checks the ability to handle edge cases like no common digits.

Common Pitfalls or Variants

Common pitfalls

Failing to handle the case where no common digits exist.
Incorrectly assuming arrays are always guaranteed to have common digits.
Not optimizing the solution with hash table lookups, resulting in slower solutions.

Follow-up variants

What if the arrays contain more than one common digit? (Handle multiple common digits)
What if the arrays contain non-digit elements? (Handle invalid inputs)
What if the input arrays have a larger length limit? (Scale the solution accordingly)

FAQ

How do I approach the Form Smallest Number From Two Digit Arrays problem?

Start by scanning both arrays for common digits. If no common digits exist, select the smallest digits from each array to form the number.

What is the optimal solution for the Form Smallest Number From Two Digit Arrays problem?

Using a hash table to find common digits efficiently allows for an optimal O(n + m) time complexity solution.

What is the time complexity of the Form Smallest Number From Two Digit Arrays problem?

The time complexity is O(n + m), where n and m are the lengths of the two arrays.

How do I handle cases where there are no common digits in the Form Smallest Number From Two Digit Arrays problem?

If no common digits exist, choose the smallest digit from each array and form the number.

What should I do if the input arrays have duplicate digits in the Form Smallest Number From Two Digit Arrays problem?

The problem guarantees that the digits in each array are unique, so duplicates should not appear in the input.

terminal

Solution

Solution 1: Enumeration

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.

1

2

3

4

5

6

7

8

9

10

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 ans

Solution 2: Hash Table or Array + Enumeration

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.

1

2

3

4

5

6

7

8

9

10

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 ans

Solution 3: Bit Operation

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$.

1

2

3

4

5

6

7

8

9

10

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 ans

Continue Practicing

#2768 number of black blocks #2367 number of arithmetic triplets #2306 naming a company