Form Smallest Number From Two Digit Arrays - Video Solutions

Problem Overview: You are given two arrays containing digits (1–9). The task is to form the smallest possible integer using digits from both arrays. If the arrays share a common digit, that digit alone forms the smallest number. Otherwise, combine the smallest digits from each array to create the smallest two-digit number.

Approach 1: Intersection and Small Pair Approach (O(n + m) time, O(1) space)

The key observation: a single-digit number is always smaller than any two-digit number. If both arrays share a common digit, that digit is automatically the smallest valid result. Use a small boolean frequency array or a hash set to record digits from the first array, then iterate through the second array to detect intersections. Track the smallest shared digit while scanning.

If no intersection exists, compute the smallest digit from each array and form two candidate numbers: a*10 + b and b*10 + a. Choose the smaller one. This method performs simple iterations and constant-time lookups using a hash table style structure. Because digits range only from 1–9, the space remains constant. The algorithm runs in linear time relative to input size and is the optimal solution.

Approach 2: Brute Force Construction (O(n × m) time, O(1) space)

The brute force approach checks every pair of digits between the two arrays. For each pair (a, b), construct both possible two-digit numbers (a*10 + b and b*10 + a) and track the smallest result. Additionally, check if a == b; if so, that digit alone can form a single-digit candidate.

This solution relies on straightforward enumeration of all possible combinations. It guarantees correctness but does unnecessary work when the arrays are large. Time complexity grows with the product of both array sizes, making it less efficient than the intersection-based strategy.

Both approaches rely on basic iteration over an array. The difference lies in how efficiently they detect shared digits and build the minimal result.

Recommended for interviews: The Intersection and Small Pair approach is what interviewers expect. It shows you recognize that a shared digit immediately produces the smallest number and that hash lookups reduce unnecessary pair checks. The brute force version is still useful as a starting point during interviews to demonstrate baseline reasoning before optimizing.