Form Smallest Number From Two Digit Arrays

Form Smallest Number From Two Digit Arrays - Problem

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

The result can be formed by concatenating digits from both arrays in any order. You want to minimize the overall numerical value of the result.

Example: If nums1 = [4,1,3] and nums2 = [5,7], possible numbers include 14, 15, 17, 34, 35, 37, 41, 43, 45, 47, 51, 53, 54, 57, 71, 73, 74, 75. The smallest is 14.

Input & Output

Example 1 — No Common Digits

$ Input: nums1 = [4,1,3], nums2 = [5,7]

› Output: 15

💡 Note: No digits appear in both arrays. The smallest from nums1 is 1, from nums2 is 5. Between 15 and 51, we choose 15.

Example 2 — Common Digit Exists

$ Input: nums1 = [3,5,2,6], nums2 = [3,1,7]

› Output: 3

💡 Note: Digit 3 appears in both arrays. Since we can form a single-digit number, 3 is smaller than any 2-digit combination.

Example 3 — Multiple Common Digits

$ Input: nums1 = [6,8,4,2], nums2 = [4,9,2,3]

› Output: 2

💡 Note: Both 4 and 2 appear in both arrays. We choose the smaller common digit: 2.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two arrays of unique digits from 1-9

Find Strategy

Check for intersection or find minimums

Optimal Result

Return smallest possible number using both arrays

Key Takeaway

🎯 Key Insight: Always check for common digits first - a single shared digit beats any 2-digit combination!

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

The key insight is to check for common digits first - if any digit appears in both arrays, it forms the smallest possible single-digit answer. Otherwise, combine the minimum digits from each array in ascending order. Best approach is Greedy with Time: O(n + m), Space: O(min(n,m)).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set Optimization	O(n + m)	O(m)	Use hash set to quickly find common digits, then generate minimal combinations
Optimal Greedy Solution	O(n + m)	O(min(n, m))	Direct solution: find intersection minimum or combine two smallest digits optimally
Brute Force - Try All Combinations	O(n × m)	O(n + m)	Generate all possible numbers using digits from both arrays and find minimum

Hash Set Optimization — Algorithm Steps

Step 1: Create hash set from nums2 for fast lookups
Step 2: Check nums1 for any digits in the hash set
Step 3: If common digit found, return minimum; else combine two smallest

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Hash Set

Create set from nums2 for O(1) lookups

Check Intersection

Scan nums1 and check against hash set

Optimal Choice

Return min common digit or best 2-digit combo

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int set2[10] = {0}; // digits 0-9
    for (int i = 0; i < nums2Size; i++) {
        set2[nums2[i]] = 1;
    }
    
    // Check for common digits
    int commonDigits[10];
    int commonCount = 0;
    for (int i = 0; i < nums1Size; i++) {
        if (set2[nums1[i]]) {
            commonDigits[commonCount++] = nums1[i];
        }
    }
    
    if (commonCount > 0) {
        int minCommon = commonDigits[0];
        for (int i = 1; i < commonCount; i++) {
            if (commonDigits[i] < minCommon) {
                minCommon = commonDigits[i];
            }
        }
        return minCommon;
    }
    
    // No common digits
    int min1 = nums1[0];
    for (int i = 1; i < nums1Size; i++) {
        if (nums1[i] < min1) {
            min1 = nums1[i];
        }
    }
    
    int min2 = nums2[0];
    for (int i = 1; i < nums2Size; i++) {
        if (nums2[i] < min2) {
            min2 = nums2[i];
        }
    }
    
    int option1 = min1 * 10 + min2;
    int option2 = min2 * 10 + min1;
    return (option1 < option2) ? option1 : option2;
}

int main() {
    char line[1000];
    int nums1[100], nums2[100];
    int nums1Size = 0, nums2Size = 0;
    
    // Parse first array
    fgets(line, sizeof(line), stdin);
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums1[nums1Size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Parse second array
    fgets(line, sizeof(line), stdin);
    ptr = strchr(line, '[') + 1;
    token = strtok(ptr, ",]");
    while (token != NULL) {
        nums2[nums2Size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums1, nums1Size, nums2, nums2Size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Single pass through both arrays with O(1) hash lookups

✓ Linear Growth

Space Complexity

O(m)

Hash set stores all digits from nums2

✓ Linear Space

9.0K Views

Medium Frequency

~8 min Avg. Time

324 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Set Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler