Teaching Kids Programming – Form Smallest Number From Two Digit Arrays (Set Intersection)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Form Smallest Number From Two Digit Arrays

We are given two lists of integers nums1 and nums2, our task is to return the minimum integer that can be obtained by concatenating any integer from nums1 and any integer from nums2, repeating digits are allowed.

Here are the steps of one algorithm:

1. Convert the lists nums1 and nums2 to sets a and b, respectively.
2. Find the intersection of a and b and store it in c.
3. If the intersection set c is not empty, return the minimum value from the set c.
4. If the intersection set c is empty, find the minimum values from sets a and b and concatenate them in two ways, and return the minimum of the two concatenated values.

Let’s go through the code step by step to understand the solution in more detail.

1
2

a = set(nums1)
b = set(nums2)

a = set(nums1)
b = set(nums2)

In the first step, the lists nums1 and nums2 are converted to sets a and b. Converting the lists to sets removes any duplicates in the lists, which is essential for finding the minimum value. Sets also provide a fast way to find the intersection of two sets.

1

c = a & b

c = a & b

In the second step, the intersection of the sets a and b is found and stored in c. The & operator is used to find the intersection of two sets. If the intersection set c is not empty, it means that there is at least one common value in the two sets. In this case, we can return the minimum value from the intersection set as the result.

1
2

if c:
    return min(c)

if c:
    return min(c)

If the intersection set c is empty, it means that there are no common values in the two sets. In this case, we need to concatenate the minimum values from sets a and b in two ways and return the minimum of the two concatenated values. The minimum values from sets a and b are found using the min() function.

1
2

ma = min(a)
mb = min(b)

ma = min(a)
mb = min(b)

The two possible concatenated values are ma * 10 + mb and mb * 10 + ma.

1

return min(ma * 10 + mb, mb * 10 + ma)

return min(ma * 10 + mb, mb * 10 + ma)

The concatenated values are multiplied by 10 to shift the digits of the second number to the left of the first number. For example, if ma is 2 and mb is 3, ma * 10 + mb becomes 23 and mb * 10 + ma becomes 32. The minimum of the two concatenated values is returned as the final result.

In conclusion, the given solution provides a simple and efficient way to solve the problem. The solution first converts the input lists to sets and finds the intersection of the two sets. If there is at least one common value in the sets, the minimum value from the intersection set is returned. If there are no common values in the sets, the minimum values from the sets are concatenated in two ways, and the minimum of the two concatenated values is returned. This solution has a time complexity of O(1), as there are at most 10 digits for each array, and the problem has a constant space scope.

The complete Python code solution is given as below:

1
2
3
4
5
6
7
8
9
10

class Solution:
    def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
        a = set(nums1)
        b = set(nums2)
        c = a & b
        if c:
            return min(c)
        ma = min(a)
        mb = min(b)
        return min(ma * 10 + mb, mb * 10 + ma)

class Solution:
    def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
        a = set(nums1)
        b = set(nums2)
        c = a & b
        if c:
            return min(c)
        ma = min(a)
        mb = min(b)
        return min(ma * 10 + mb, mb * 10 + ma)

We can also do this:

1

return min(ma, mb) * 10 + max(ma, mb)

return min(ma, mb) * 10 + max(ma, mb)

–EOF (The Ultimate Computing & Technology Blog) —