Problem

Given two arrays of unique digits nums1 and nums2, return thesmallest number that contains at least one digit from each array.

Examples

Example 1

1
2
3

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

1
2
3

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.

Solution

Method 1 – Brute Force and Set Intersection

Intuition

The smallest number containing at least one digit from each array can be formed by either:

  • A two-digit number using the smallest digit from each array (in both orders), or
  • The smallest common digit in both arrays (as a one-digit number).

Approach

  1. Find the smallest digit in nums1 and nums2.
  2. Check if there is any common digit between the two arrays. If so, the smallest such digit is the answer.
  3. Otherwise, return the smaller of the two possible two-digit numbers formed by combining the smallest digits from each array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int minNumber(vector<int>& nums1, vector<int>& nums2) {
        int ans = 100;
        for (int x : nums1)
            for (int y : nums2)
                if (x == y) ans = min(ans, x);
                else ans = min(ans, min(x * 10 + y, y * 10 + x));
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

type Solution struct{}
func (Solution) minNumber(nums1, nums2 []int) int {
    ans := 100
    for _, x := range nums1 {
        for _, y := range nums2 {
            if x == y {
                if x < ans { ans = x }
            } else {
                if x*10+y < ans { ans = x*10 + y }
                if y*10+x < ans { ans = y*10 + x }
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int minNumber(int[] nums1, int[] nums2) {
        int ans = 100;
        for (int x : nums1)
            for (int y : nums2)
                if (x == y) ans = Math.min(ans, x);
                else ans = Math.min(ans, Math.min(x * 10 + y, y * 10 + x));
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun minNumber(nums1: IntArray, nums2: IntArray): Int {
        var ans = 100
        for (x in nums1) {
            for (y in nums2) {
                if (x == y) ans = minOf(ans, x)
                else ans = minOf(ans, x * 10 + y, y * 10 + x)
            }
        }
        return ans
    }
}
 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 x in nums1:
            for y in nums2:
                if x == y:
                    ans = min(ans, x)
                else:
                    ans = min(ans, x * 10 + y, y * 10 + x)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn min_number(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let mut ans = 100;
        for &x in &nums1 {
            for &y in &nums2 {
                if x == y {
                    ans = ans.min(x);
                } else {
                    ans = ans.min(x * 10 + y).min(y * 10 + x);
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
  minNumber(nums1: number[], nums2: number[]): number {
    let ans = 100;
    for (const x of nums1) {
      for (const y of nums2) {
        if (x === y) ans = Math.min(ans, x);
        else ans = Math.min(ans, x * 10 + y, y * 10 + x);
      }
    }
    return ans;
  }
}

Complexity

  • ⏰ Time complexity: O(m * n), where m and n are the lengths of nums1 and nums2, since all pairs are checked.
  • 🧺 Space complexity: O(1), as only a few variables are used.