Form Smallest Number From Two Digit Arrays solution and explanation
9 more videos on this problem
Leetcode 2605: Form Smallest Number From Two Digit ArraysAlgorithms Casts · 5:56 · 509 views
6327. Form Smallest Number From Two Digit Arrays || Leetcode Solutions || Biweekly Contest 101CodeCake · 0:26 · 400 views
2605. Form Smallest Number From Two Digit Arrays || In Java || Leetcode || Easy Way #leetcodeQuick Learning With Sree · 9:10 · 295 views
2605. Form Smallest Number From Two Digit Arrays (Leetcode Easy)Programming Live with Larry · 3:00 · 262 views
2605.||Form Smallest Number From Two Digit Arrays || c++ in Hindi || beweekly contest 101Code Coder · 8:13 · 240 views
Leetcode Biweekly Contest 101 | 2605. Form Smallest Number From Two Digit Arrays | SolutionMd Zuhair · 2:15 · 222 views
LeetCode Biweekly Contest 101 | 6327. Form Smallest Number From Two Digit Arrays | PythonBayu Aji · 3:12 · 195 views
Biweekly Contest 101 | Form Smallest Number From Two Digit ArraysLet us code · 4:49 · 98 views
Form Smallest Number From Two Digit Arrays #LeetCode #java #coding #intervewQuestions #dsaCodeVia · 3:40 · 89 views
2605. Form Smallest Number From Two Digit Arrays | Easy | Leetcode | Biweekly Contest 101.Optimization · 3:05 · 53 views
The problem
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 <= 91 <= nums1[i], nums2[i] <= 9- All digits in each array are unique.
Approach overview
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.
Approach 1: Intersection and Small Pair Approach
This approach involves two steps:
- Check for common elements between the two arrays. If a common element exists, that digit itself is the smallest number possible.
- If there is no common digit, form the smallest two-digit number by selecting the smallest digit from each array.
def smallest_number(nums1, nums2):
common = set(nums1) & set(nums2)
if common:
return min(common)
min1, min2 = min(nums1), min(nums2)
return min(min1, min2) * 10 + max(min1, min2)
nums1 = [3, 5, 2, 6]
nums2 = [3, 1, 7]
print(smallest_number(nums1, nums2)) # Output: 3import java.util.HashSet;
public class SmallestNumber {
public int smallestNumber(int[] nums1, int[] nums2) {
HashSet<Integer> set = new HashSet<>();
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
for (int num : nums1) {
set.add(num);
min1 = Math.min(min1, num);
}
for (int num : nums2) {
if (set.contains(num)) return num;
min2 = Math.min(min2, num);
}
return Math.min(min1, min2) * 10 + Math.max(min1, min2);
}
public static void main(String[] args) {
SmallestNumber sn = new SmallestNumber();
int[] nums1 = {3, 5, 2, 6};
int[] nums2 = {3, 1, 7};
System.out.println(sn.smallestNumber(nums1, nums2)); // Output: 3
}
}#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int smallestNumber(vector<int>& nums1, vector<int>& nums2) {
vector<int> common(10, 0);
int min1 = INT_MAX, min2 = INT_MAX;
for(int num : nums1) {
common[num] = 1;
min1 = min(min1, num);
}
for(int num : nums2) {
if(common[num]) return num;
min2 = min(min2, num);
}
return min(min1, min2) * 10 + max(min1, min2);
}
int main() {
vector<int> nums1 = {3, 5, 2, 6};
vector<int> nums2 = {3, 1, 7};
int result = smallestNumber(nums1, nums2); // Output: 3
return 0;
}function smallestNumber(nums1, nums2) {
const set1 = new Set(nums1);
let min1 = Math.min(...nums1);
let min2 = Infinity;
for (let num of nums2) {
if (set1.has(num)) return num;
min2 = Math.min(min2, num);
}
return Math.min(min1, min2) * 10 + Math.max(min1, min2);
}
console.log(smallestNumber([3, 5, 2, 6], [3, 1, 7])); // Output: 3#include <stdio.h>
#include <limits.h>
int smallestNumber(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int common[10] = {0};
int min1 = INT_MAX, min2 = INT_MAX;
for(int i = 0; i < nums1Size; i++) {
common[nums1[i]] = 1;
if(nums1[i] < min1) min1 = nums1[i];
}
for(int i = 0; i < nums2Size; i++) {
if(common[nums2[i]] == 1) return nums2[i];
if(nums2[i] < min2) min2 = nums2[i];
}
if(min1 < min2) return min1 * 10 + min2;
return min2 * 10 + min1;
}
int main() {
int nums1[] = {3, 5, 2, 6};
int nums2[] = {3, 1, 7};
printf("%d\n", smallestNumber(nums1, 4, nums2, 3)); // Output: 3
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int SmallestNumber(int[] nums1, int[] nums2) {
HashSet<int> set = new HashSet<int>(nums1);
int min1 = int.MaxValue, min2 = int.MaxValue;
foreach (int num in nums1) {
if (num < min1) min1 = num;
}
foreach (int num in nums2) {
if (set.Contains(num)) return num;
if (num < min2) min2 = num;
}
return Math.Min(min1, min2) * 10 + Math.Max(min1, min2);
}
public static void Main() {
Solution sol = new Solution();
int[] nums1 = {3, 5, 2, 6};
int[] nums2 = {3, 1, 7};
Console.WriteLine(sol.SmallestNumber(nums1, nums2)); // Output: 3
}
}This Python solution utilizes set operations to find common digits efficiently. If a common digit is present, it's the smallest number possible. Otherwise, the solution constructs a two-digit number from the smallest digits of each array.
Time Complexity: O(n + m).
Space Complexity: O(1) as the set operation is efficient for small input sizes.
Approach 2: Brute Force Construction
This approach simply tries all combinations by looping through both arrays to find a suitable number containing elements from each, though it's less efficient than the intersection approach.
def smallest_number(nums1, nums2):
result = 99
for x in nums1:
for y in nums2:
result = min(result, x * 10 + y, y * 10 + x)
return result
nums1 = [3, 5, 2, 6]
nums2 = [3, 1, 7]
print(smallest_number(nums1, nums2)) # Output: 3public class SmallestNumberBruteForce {
public int smallestNumber(int[] nums1, int[] nums2) {
int minNum = 99;
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
int num1 = nums1[i] * 10 + nums2[j];
int num2 = nums2[j] * 10 + nums1[i];
minNum = Math.min(minNum, Math.min(num1, num2));
}
}
return minNum;
}
public static void main(String[] args) {
SmallestNumberBruteForce sbr = new SmallestNumberBruteForce();
int[] nums1 = {3, 5, 2, 6};
int[] nums2 = {3, 1, 7};
System.out.println(sbr.smallestNumber(nums1, nums2)); // Output: 3
}
}#include <vector>
#include <algorithm>
using namespace std;
int smallestNumber(vector<int>& nums1, vector<int>& nums2) {
int minNum = 99;
for (size_t i = 0; i < nums1.size(); i++) {
for (size_t j = 0; j < nums2.size(); j++) {
int num1 = nums1[i] * 10 + nums2[j];
int num2 = nums2[j] * 10 + nums1[i];
minNum = min({minNum, num1, num2});
}
}
return minNum;
}
int main() {
vector<int> nums1 = {3, 5, 2, 6};
vector<int> nums2 = {3, 1, 7};
int result = smallestNumber(nums1, nums2); // Output: 3
return 0;
}function smallestNumber(nums1, nums2) {
let result = 99;
for (let x of nums1) {
for (let y of nums2) {
result = Math.min(result, x * 10 + y, y * 10 + x);
}
}
return result;
}
console.log(smallestNumber([3, 5, 2, 6], [3, 1, 7])); // Output: 3#include <stdio.h>
int smallestNumber(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int result = 99; // The largest two-digit number
for (int i = 0; i < nums1Size; i++) {
for (int j = 0; j < nums2Size; j++) {
int num1 = nums1[i] * 10 + nums2[j];
int num2 = nums2[j] * 10 + nums1[i];
if (num1 < result) result = num1;
if (num2 < result) result = num2;
}
}
return result;
}
int main() {
int nums1[] = {3, 5, 2, 6};
int nums2[] = {3, 1, 7};
printf("%d\n", smallestNumber(nums1, 4, nums2, 3)); // Output: 3
return 0;
}using System;
public class Solution {
public int SmallestNumber(int[] nums1, int[] nums2) {
int result = 99;
foreach (int num1 in nums1) {
foreach (int num2 in nums2) {
result = Math.Min(result, Math.Min(num1 * 10 + num2, num2 * 10 + num1));
}
}
return result;
}
public static void Main() {
Solution sol = new Solution();
int[] nums1 = {3, 5, 2, 6};
int[] nums2 = {3, 1, 7};
Console.WriteLine(sol.SmallestNumber(nums1, nums2)); // Output: 3
}
}This Python approach is straightforward, trying each digit from nums1 with each from nums2 to check both their possible two-digit combinations. It keeps the smallest value found.
Time Complexity: O(n * m).
Space Complexity: O(1), using only integer variables.
Approach 3: Enumeration
We observe that if there are the same numbers in the arrays nums1 and nums2, then the minimum of the same numbers is the smallest number. Otherwise, we take the number a in the array nums1 and the number b in the array nums2, and concatenate the two numbers a and b into two numbers, and take the smaller number.
The time complexity is O(m times n), and the space complexity is O(1), where m and n are the lengths of the arrays nums1 and nums2.
function minNumber(nums1: number[], nums2: number[]): number {
let ans = 100;
for (const a of nums1) {
for (const b of nums2) {
if (a === b) {
ans = Math.min(ans, a);
} else {
ans = Math.min(ans, a * 10 + b, b * 10 + a);
}
}
}
return ans;
}func minNumber(nums1 []int, nums2 []int) int {
ans := 100
for _, a := range nums1 {
for _, b := range nums2 {
if a == b {
ans = min(ans, a)
} else {
ans = min(ans, min(a*10+b, b*10+a))
}
}
}
return ans
}impl Solution {
pub fn min_number(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let mut ans = 100;
for &a in &nums1 {
for &b in &nums2 {
if a == b {
ans = std::cmp::min(ans, a);
} else {
ans = std::cmp::min(ans, std::cmp::min(a * 10 + b, b * 10 + a));
}
}
}
ans
}
}Approach 4: Hash Table or Array + Enumeration
We can use a hash table or array to record the numbers in the arrays nums1 and nums2, and then enumerate 1 \sim 9. If i appears in both arrays, then i is the smallest number. Otherwise, we take the number a in the array nums1 and the number b in the array nums2, and concatenate the two numbers a and b into two numbers, and take the smaller number.
The time complexity is (m + n), and the space complexity is O(C). Where m and n are the lengths of the arrays nums1 and nums2 respectively; and C is the range of the numbers in the arrays nums1 and nums2, and the range in this problem is C = 10.
function minNumber(nums1: number[], nums2: number[]): number {
const s1: boolean[] = new Array(10).fill(false);
const s2: boolean[] = new Array(10).fill(false);
for (const x of nums1) {
s1[x] = true;
}
for (const x of nums2) {
s2[x] = true;
}
let a = 0;
let b = 0;
for (let i = 1; i < 10; ++i) {
if (s1[i] && s2[i]) {
return i;
}
if (a === 0 && s1[i]) {
a = i;
}
if (b === 0 && s2[i]) {
b = i;
}
}
return Math.min(a * 10 + b, b * 10 + a);
}func minNumber(nums1 []int, nums2 []int) int {
s1 := [10]bool{}
s2 := [10]bool{}
for _, x := range nums1 {
s1[x] = true
}
for _, x := range nums2 {
s2[x] = true
}
a, b := 0, 0
for i := 1; i < 10; i++ {
if s1[i] && s2[i] {
return i
}
if a == 0 && s1[i] {
a = i
}
if b == 0 && s2[i] {
b = i
}
}
return min(a*10+b, b*10+a)
}use std::collections::HashMap;
impl Solution {
pub fn min_number(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let mut h1: HashMap<i32, bool> = HashMap::new();
for &n in &nums1 {
h1.insert(n, true);
}
let mut h2: HashMap<i32, bool> = HashMap::new();
for &n in &nums2 {
h2.insert(n, true);
}
let mut a = 0;
let mut b = 0;
for i in 1..10 {
if h1.contains_key(&i) && h2.contains_key(&i) {
return i;
}
if a == 0 && h1.contains_key(&i) {
a = i;
}
if b == 0 && h2.contains_key(&i) {
b = i;
}
}
std::cmp::min(a * 10 + b, b * 10 + a)
}
}Approach 5: Bit Operation
Since the range of the numbers is 1 \sim 9, we can use a binary number with a length of 10 to represent the numbers in the arrays nums1 and nums2. We use mask1 to represent the numbers in the array nums1, and use mask2 to represent the numbers in the array nums2.
If the number mask obtained by performing a bitwise AND operation on mask1 and mask2 is not equal to 0, then we extract the position of the last 1 in the number mask, which is the smallest number.
Otherwise, we extract the position of the last 1 in mask1 and mask2 respectively, and denote them as a and b, respectively. Then the smallest number is min(a times 10 + b, b times 10 + a).
The time complexity is O(m + n), and the space complexity is O(1). Where m and n are the lengths of the arrays nums1 and nums2 respectively.
function minNumber(nums1: number[], nums2: number[]): number {
let mask1: number = 0;
let mask2: number = 0;
for (const x of nums1) {
mask1 |= 1 << x;
}
for (const x of nums2) {
mask2 |= 1 << x;
}
const mask = mask1 & mask2;
if (mask !== 0) {
return numberOfTrailingZeros(mask);
}
const a = numberOfTrailingZeros(mask1);
const b = numberOfTrailingZeros(mask2);
return Math.min(a * 10 + b, b * 10 + a);
}
function numberOfTrailingZeros(i: number): number {
let y = 0;
if (i === 0) {
return 32;
}
let n = 31;
y = i << 16;
if (y != 0) {
n = n - 16;
i = y;
}
y = i << 8;
if (y != 0) {
n = n - 8;
i = y;
}
y = i << 4;
if (y != 0) {
n = n - 4;
i = y;
}
y = i << 2;
if (y != 0) {
n = n - 2;
i = y;
}
return n - ((i << 1) >>> 31);
}func minNumber(nums1 []int, nums2 []int) int {
var mask1, mask2 uint
for _, x := range nums1 {
mask1 |= 1 << x
}
for _, x := range nums2 {
mask2 |= 1 << x
}
if mask := mask1 & mask2; mask != 0 {
return bits.TrailingZeros(mask)
}
a, b := bits.TrailingZeros(mask1), bits.TrailingZeros(mask2)
return min(a*10+b, b*10+a)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Intersection and Small Pair Approach | Time Complexity: O(n + m). |
| Brute Force Construction | Time Complexity: O(n * m). |
| Enumeration | – |
| Hash Table or Array + Enumeration | – |
| Bit Operation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Intersection and Small Pair Approach | O(n + m) | O(1) | Best general solution. Quickly detects common digits and builds the minimal number efficiently. |
| Brute Force Construction | O(n × m) | O(1) | Useful for understanding the problem or when constraints are extremely small. |
Frequently asked questions
Is Form Smallest Number From Two Digit Arrays easy or hard?
Form Smallest Number From Two Digit Arrays is classified as an Easy problem on LeetCode. The challenge focuses on recognizing that a shared digit forms the smallest possible number and applying a simple hash-based lookup to avoid unnecessary pair comparisons.
Form Smallest Number From Two Digit Arrays Python/Java solution
In Python or Java, the common solution builds a set or boolean array from the first list of digits and scans the second list to detect intersections. If a shared digit exists, return the smallest one; otherwise compute the minimal two-digit number from the smallest digits in both arrays.
How to solve Form Smallest Number From Two Digit Arrays in O(n)?
Store digits from the first array in a boolean array or hash set. While scanning the second array, check if any digit already exists in the set. If a match appears, track the smallest shared digit. If no match exists, compute the smallest digit in each array and combine them to form the minimal two-digit number.
What is the best approach for Form Smallest Number From Two Digit Arrays?
The best approach is the Intersection and Small Pair method. First detect whether the two arrays share a common digit using a hash set or small frequency array. If a common digit exists, return the smallest one. Otherwise combine the smallest digits from each array to form the smallest two‑digit number. This runs in O(n + m) time and O(1) space.
Is Form Smallest Number From Two Digit Arrays asked at Google/Amazon/Meta?
This problem represents a typical easy-level interview pattern involving arrays and hash lookups. Similar digit-combination and set-intersection questions appear in interviews at companies like Amazon, Google, and Meta to test basic data structure reasoning and edge-case handling.
What data structure is used in Form Smallest Number From Two Digit Arrays?
A hash table or boolean frequency array is commonly used to detect shared digits between the two arrays. Because digits are limited to 1–9, a fixed-size array of length 10 works efficiently and provides constant-time membership checks.
What is the time complexity of Form Smallest Number From Two Digit Arrays?
The optimal solution runs in O(n + m) time where n and m are the lengths of the two arrays. The algorithm scans each array once and performs constant-time lookups to check for intersections. Space complexity is O(1) because the digit range is limited to 1–9.