# Form Smallest Number From Two Digit Arrays
**Difficulty:** EASY
[External](https://leetcode.com/problems/form-smallest-number-from-two-digit-arrays)
Canonical: https://scaleengineer.com/dsa/problems/form-smallest-number-from-two-digit-arrays
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, Hash Table
**Companies:** [Tinkoff](https://scaleengineer.com/companies/tinkoff)
---
## Problem
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**.

# Approaches
## Brute-Force with Nested Loops
This is a straightforward approach that directly translates the problem's conditions into code. It checks for common digits using nested loops and separately finds the minimums of each array to handle the case where no common digits exist.
**Time:** O(N * M), where N and M are the lengths of `nums1` and `nums2` respectively. The nested loops for finding the common digit dominate the runtime. The subsequent loops to find minimums take O(N + M), which is subsumed by O(N*M). · **Space:** O(1), as it only uses a constant amount of extra space for variables.
**Pros:** Simple to understand and implement.; Requires no extra space besides a few variables.
**Cons:** The time complexity of O(N*M) is inefficient for larger inputs, although it passes given the problem's constraints.
### Explanation
The smallest possible number can either be a single digit (if a digit exists in both arrays) or a two-digit number. A single-digit number is always smaller than any two-digit number. Therefore, the primary goal is to find if there's a common digit, and if so, which one is the smallest.

This brute-force algorithm proceeds as follows:
1.  First, it attempts to find the smallest common digit by comparing every digit from `nums1` with every digit from `nums2`.
2.  It uses a variable, `minCommon`, initialized to a value larger than any digit (like 10), to keep track of the smallest common digit found.
3.  If a common digit is found, `minCommon` will hold the smallest such digit. Since this is a single-digit number, it must be the smallest possible number we can form. The algorithm returns this value.
4.  If the loops complete and `minCommon` hasn't changed, it means there are no common digits. In this scenario, the smallest number must be a two-digit number.
5.  To form the smallest two-digit number, we must use the smallest possible digit for the tens place. This requires finding the minimum digit from `nums1` (`min1`) and the minimum digit from `nums2` (`min2`).
6.  The two candidate numbers are `min1` followed by `min2` and `min2` followed by `min1`. The algorithm returns the smaller of these two.

```java
class Solution {
    public int minNumber(int[] nums1, int[] nums2) {
        int minCommon = 10;
        for (int x : nums1) {
            for (int y : nums2) {
                if (x == y) {
                    minCommon = Math.min(minCommon, x);
                }
            }
        }

        if (minCommon != 10) {
            return minCommon;
        }

        int min1 = 10;
        for (int x : nums1) {
            min1 = Math.min(min1, x);
        }

        int min2 = 10;
        for (int x : nums2) {
            min2 = Math.min(min2, x);
        }

        return Math.min(min1 * 10 + min2, min2 * 10 + min1);
    }
}
```
### Algorithm
*   Initialize `minCommon` to a value greater than any possible digit (e.g., 10).
*   Iterate through each digit `d1` in `nums1`.
*   Inside this loop, iterate through each digit `d2` in `nums2`.
*   If `d1` is equal to `d2`, update `minCommon = min(minCommon, d1)`.
*   After the nested loops, check if `minCommon` was updated (i.e., `minCommon < 10`). If so, a common digit was found, and the smallest one is the answer. Return `minCommon`.
*   If no common digit was found, find the minimum digit `min1` in `nums1` and `min2` in `nums2` by iterating through them separately.
*   The result is the smallest two-digit number that can be formed. Return `min(min1 * 10 + min2, min2 * 10 + min1)`.

## Sorting and Two Pointers
This approach improves the search for a common digit by sorting the arrays first. This allows for a linear-time scan using two pointers to find the smallest common digit.
**Time:** O(N log N + M log M), where N and M are the array lengths. Sorting is the most time-consuming part. The subsequent two-pointer scan takes O(N + M), which is dominated by the sorting time. · **Space:** O(log N + log M) to O(N + M), depending on the space used by the sorting algorithm. For instance, Java's `Arrays.sort` for primitives has an average space complexity of O(log N).
**Pros:** More efficient than the brute-force approach for larger arrays.; The logic is clean and leverages a standard algorithm (two pointers on sorted arrays).
**Cons:** The time complexity is dominated by sorting, which may not be the most optimal for this problem.; Sorting modifies the input arrays or requires extra space, depending on the implementation.
### Explanation
By sorting the arrays, we can find both the minimum elements and the common elements more efficiently than a brute-force search.

The algorithm is as follows:
1.  Sort both `nums1` and `nums2` in ascending order. This brings the smallest elements to the front and groups identical elements (if any) together, making comparisons efficient.
2.  To find the smallest common digit, use a two-pointer technique. One pointer `i` traverses `nums1`, and another pointer `j` traverses `nums2`.
3.  Compare the elements at the current pointers. If `nums1[i]` and `nums2[j]` are equal, we've found a common digit. Because the arrays are sorted, this must be the smallest common digit, so we can return it immediately.
4.  If the elements are not equal, we advance the pointer pointing to the smaller element, as that smaller element cannot be a common digit with the current larger element.
5.  If the two-pointer scan completes without finding any common elements, we proceed to form a two-digit number. Since the arrays are sorted, the smallest element of `nums1` is `nums1[0]` and the smallest of `nums2` is `nums2[0]`. The result is the minimum of the two numbers formed by concatenating these digits.

```java
import java.util.Arrays;

class Solution {
    public int minNumber(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int i = 0, j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                return nums1[i]; // Smallest common digit found
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        
        // No common digit found
        int min1 = nums1[0];
        int min2 = nums2[0];
        return Math.min(min1 * 10 + min2, min2 * 10 + min1);
    }
}
```
### Algorithm
*   Sort both `nums1` and `nums2` in non-decreasing order.
*   Initialize two pointers, `i` for `nums1` and `j` for `nums2`, both starting at 0.
*   Iterate while both pointers are within their respective array bounds:
    *   If `nums1[i] == nums2[j]`, a common digit is found. Since the arrays are sorted, this is the smallest common digit. Return it.
    *   If `nums1[i] < nums2[j]`, increment `i` to find a potentially larger matching digit in `nums1`.
    *   Else (`nums1[i] > nums2[j]`), increment `j`.
*   If the loop finishes without returning, no common digits exist.
*   The smallest digit in `nums1` is `nums1[0]` and in `nums2` is `nums2[0]`. Return the smaller of the two-digit numbers formed by them: `min(nums1[0] * 10 + nums2[0], nums2[0] * 10 + nums1[0])`.

## Linear Time with Frequency Array
This is the most efficient approach, achieving linear time complexity. It uses a frequency array (or a hash set) to keep track of digits from one array and then iterates through the second array to find common digits and minimums in just two passes.
**Time:** O(N + M), where N and M are the lengths of the arrays. We iterate through each array exactly once. · **Space:** O(1), as the `seen` array has a fixed size of 10, which is constant and does not depend on the input array sizes.
**Pros:** Optimal time complexity of O(N+M).; Uses constant extra space because the range of digits is fixed and small.
**Cons:** Slightly more complex than the brute-force approach due to the use of an auxiliary data structure.
### Explanation
This method avoids both nested loops and sorting by using an auxiliary data structure to store information about the digits. Since the digits are constrained to be between 1 and 9, a simple boolean array of size 10 serves as a highly efficient hash set.

The algorithm combines finding the minimums and the common digits into two separate linear passes:
1.  **Process `nums1`:** Iterate through `nums1` once. During this pass, do two things: find the minimum digit in `nums1` (`min1`) and mark the presence of each digit in the `seen` boolean array.
2.  **Process `nums2`:** Iterate through `nums2` once. During this pass, do two things: find the minimum digit in `nums2` (`min2`) and check for common digits. A digit `d` from `nums2` is common if `seen[d]` is true. Keep track of the smallest common digit found in a variable `minCommon`.
3.  **Determine Result:** After the two passes, if `minCommon` has been updated, it holds the smallest common digit, which is the answer. If not, no common digits exist, and the answer is the smallest two-digit number formed by `min1` and `min2`.

This approach is optimal because it processes each element in the input arrays a constant number of times.

```java
class Solution {
    public int minNumber(int[] nums1, int[] nums2) {
        int min1 = 10;
        boolean[] seen = new boolean[10];
        for (int x : nums1) {
            min1 = Math.min(min1, x);
            seen[x] = true;
        }

        int min2 = 10;
        int minCommon = 10;
        for (int x : nums2) {
            min2 = Math.min(min2, x);
            if (seen[x]) {
                minCommon = Math.min(minCommon, x);
            }
        }

        if (minCommon != 10) {
            return minCommon;
        }

        return Math.min(min1 * 10 + min2, min2 * 10 + min1);
    }
}
```
### Algorithm
*   Initialize `min1 = 10` and a boolean array `seen` of size 10 to all `false`.
*   Iterate through `nums1`. For each digit `d`, update `min1 = min(min1, d)` and set `seen[d] = true`.
*   Initialize `min2 = 10` and `minCommon = 10`.
*   Iterate through `nums2`. For each digit `d`, update `min2 = min(min2, d)`. Also, check if `seen[d]` is true. If it is, update `minCommon = min(minCommon, d)`.
*   After both loops, if `minCommon` is not 10, it holds the smallest common digit. Return `minCommon`.
*   Otherwise, no common digits exist. Return the smallest two-digit number formed from the minimums: `min(min1 * 10 + min2, min2 * 10 + min1)`.

# Solutions
### Java

```java
class Solution {
public
  int minNumber(int[] nums1, int[] nums2) {
    int ans = 100;
    for (int a : nums1) {
      for (int b : nums2) {
        if (a == b) {
          ans = Math.min(ans, a);
        } else {
          ans = Math.min(ans, Math.min(a * 10 + b, b * 10 + a));
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minNumber(vector<int> &nums1, vector<int> &nums2) {
    int ans = 100;
    for (int a : nums1) {
      for (int b : nums2) {
        if (a == b) {
          ans = min(ans, a);
        } else {
          ans = min({ans, a * 10 + b, b * 10 + a});
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
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

```