Form Smallest Number From Two Digit Arrays

EASY

Description

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

Checkout 3 different approaches to solve Form Smallest Number From Two Digit Arrays. Click on different approaches to view the approach and algorithm in detail.

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.

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

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:

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

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);
    }
}

Complexity Analysis

Time Complexity: O(N + M), where N and M are the lengths of the arrays. We iterate through each array exactly once.Space Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Form Smallest Number From Two Digit Arrays. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Form Smallest Number From Two Digit Arrays

Patterns:

Enumeration

Data Structures:

ArrayHash Table

Companies:

Tinkoff |