Form Smallest Number From Two Digit Arrays

Easy
1075.

Form Smallest Number From Two Digit Arrays

Form Smallest Number From Two Digit Arrays is an easy coding problem on arrays, hash table and enumeration, asked in Amazon, Google and Capgemini interviews.

nums1 and nums2 each hold distinct digits from 1 to 9.

Return the smallest positive integer that contains at least one digit from nums1 and at least one digit from nums2.

Example 1

Input
nums1 = [4,1,3], nums2 = [5,7]
Output
15
Explanation
No shared digit, so pair the two smallest: `15` beats `51`.

Example 2

Input
nums1 = [3,5,2,6], nums2 = [3,1,7]
Output
3
Explanation
`3` is in both arrays, so one digit suffices.

Example 3

Input
nums1 = [9], nums2 = [2]
Output
29

Constraints

  • 1 <= nums1.length, nums2.length <= 9
  • 1 <= nums1[i], nums2[i] <= 9
  • All digits in each array are unique.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var minNumber = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Form Smallest Number From Two Digit Arrays — Solution

Form Smallest Number From Two Digit Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Form Smallest Number From Two Digit Arrays is an easy coding problem on arrays, hash table and enumeration, asked in Amazon, Google and Capgemini interviews.

Problem statement

nums1 and nums2 each hold distinct digits from 1 to 9.

Return the smallest positive integer that contains at least one digit from nums1 and at least one digit from nums2.

Example 1

Input: nums1 = [4,1,3], nums2 = [5,7]
Output: 15
Explanation: No shared digit, so pair the two smallest: `15` beats `51`.

Example 2

Input: nums1 = [3,5,2,6], nums2 = [3,1,7]
Output: 3
Explanation: `3` is in both arrays, so one digit suffices.

Example 3

Input: nums1 = [9], nums2 = [2]
Output: 29

Constraints

  • 1 <= nums1.length, nums2.length <= 9
  • 1 <= nums1[i], nums2[i] <= 9
  • All digits in each array are unique.

Hints for Form Smallest Number From Two Digit Arrays

  1. Hint 1

    If any digit appears in both arrays, a one-digit answer is possible — take the smallest such digit.

  2. Hint 2

    Otherwise the answer has exactly two digits, one from each array.

  3. Hint 3

    Use the smallest digit of each and try both orders.

How to solve Form Smallest Number From Two Digit Arrays

A shared digit gives a one-digit answer, and one digit always beats two — so take the smallest common digit if there is one. Otherwise pick the smallest digit from each array and return the smaller of the two arrangements.

Approach

  1. Find the smallest digit present in both arrays; return it if one exists.
  2. Otherwise take a = min(nums1) and b = min(nums2).
  3. Return min(10a + b, 10b + a).

Why it works

Fewer digits always wins for positive integers, which is why the shared-digit case is checked first and needs no comparison against any two-digit candidate. In the two-digit case, using anything but the minimum of each array can only make one of the two positions larger, so the smallest digits are forced and only their order is a real choice.

Complexity

  • Time — O(n · m), or O(n + m) with a set
  • Space — O(1)

Pitfalls

  • A shared digit beats every two-digit answer, however small the digits.
  • Both orders must be tried: min(nums1) is not always the leading digit.
  • The digits are 1–9, so there is no leading-zero case to worry about.

Reference solution

Python

from typing import List

def minNumber(nums1: List[int], nums2: List[int]) -> int:
    shared = set(nums1) & set(nums2)
    if shared:
        return min(shared)
    a, b = min(nums1), min(nums2)
    return min(a * 10 + b, b * 10 + a)

Java

public static int minNumber(int[] nums1, int[] nums2) {
    int shared = 10;
    for (int x : nums1) {
        for (int y : nums2) {
            if (x == y && x < shared) shared = x;
        }
    }
    if (shared < 10) return shared;
    int a = 10, b = 10;
    for (int x : nums1) a = Math.min(a, x);
    for (int y : nums2) b = Math.min(b, y);
    return Math.min(a * 10 + b, b * 10 + a);
}

C++

int minNumber(vector<int>& nums1, vector<int>& nums2) {
    int shared = 10;
    for (int x : nums1) {
        for (int y : nums2) {
            if (x == y && x < shared) shared = x;
        }
    }
    if (shared < 10) return shared;
    int a = 10, b = 10;
    for (int x : nums1) a = min(a, x);
    for (int y : nums2) b = min(b, y);
    return min(a * 10 + b, b * 10 + a);
}

JavaScript

var minNumber = function(nums1, nums2) {
    var shared = 10, i, j;
    for (i = 0; i < nums1.length; i++) {
        for (j = 0; j < nums2.length; j++) {
            if (nums1[i] === nums2[j] && nums1[i] < shared) shared = nums1[i];
        }
    }
    if (shared < 10) return shared;
    var a = 10, b = 10;
    for (i = 0; i < nums1.length; i++) if (nums1[i] < a) a = nums1[i];
    for (j = 0; j < nums2.length; j++) if (nums2[j] < b) b = nums2[j];
    var first = a * 10 + b, second = b * 10 + a;
    return first < second ? first : second;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets