Leetcode 2605: Form Smallest Number From Two Digit Arrays
You are given two arrays nums1 and nums2, both containing unique digits. Your task is to find the smallest possible number that contains at least one digit from both arrays. If there are common digits between the two arrays, the smallest common digit will be the answer. If no common digit exists, return the smallest number formed by taking the smallest digit from each array.
Problem
Approach
Steps
Complexity
Input: You are given two arrays nums1 and nums2. Both arrays consist of unique digits between 1 and 9.
Example: nums1 = [8, 2, 5], nums2 = [6, 1]
Constraints:
• 1 <= nums1.length, nums2.length <= 9
• 1 <= nums1[i], nums2[i] <= 9
• All digits in each array are unique.
Output: Return the smallest number that contains at least one digit from each array. If there is a common digit between the two arrays, return it. If not, return the smallest number formed by combining the smallest digit from each array.
Example: Output: 15
Constraints:
• Output should be a single integer.
Goal: To find the smallest number containing at least one digit from each array.
Steps:
• Check if there is any common digit between nums1 and nums2.
• If there is a common digit, return that digit as the result.
• If no common digit exists, return the smallest number formed by combining the smallest digits from both arrays.
Goal: Ensure that the solution works efficiently with small arrays, as both arrays contain at most 9 elements.
Steps:
• nums1.length, nums2.length <= 9
• nums1[i], nums2[i] <= 9
Assumptions:
• The arrays nums1 and nums2 will always contain unique digits.
• Input: nums1 = [8, 2, 5], nums2 = [6, 1]
• Explanation: There are no common digits between the arrays. The smallest number formed by combining the smallest digits from nums1 and nums2 is 15, which is the correct answer.
• Input: nums1 = [1, 2, 3], nums2 = [3, 4, 5]
• Explanation: The common digit between the two arrays is 3. Therefore, the smallest number that contains a digit from both arrays is 3.
Approach: To solve the problem, we first check for common digits between the two arrays. If there is one, we return that digit. Otherwise, we return the smallest number formed by combining the smallest digits from both arrays.
Observations:
• The problem involves checking for common digits and then determining the smallest possible number.
• We can efficiently check for common digits by using sets or direct comparison between the two arrays.
Steps:
• Convert both arrays into sets for quick lookup of common digits.
• Check if there are any common digits between the two sets.
• If a common digit exists, return that digit as the result.
• If no common digit exists, find the smallest digits from both arrays and return the smallest number formed by them.
Empty Inputs:
• There will be no empty inputs as both nums1 and nums2 contain at least one digit.
Large Inputs:
• Both arrays can have at most 9 digits, so the input size is small.
Special Values:
• Consider cases where the arrays share one or more common digits.
Constraints:
• Ensure that the solution works for all cases with unique digits between 1 and 9.
int minNumber(vector<int>& nums1, vector<int>& nums2) {
int num1 = nums1[0];
set<int> cnt;
int mn = 10;
for(int i = 0; i < nums1.size(); i++) {
cnt.insert(nums1[i]);
num1 = min(nums1[i], num1);
}
int num2 = nums2[0];
for(int i = 0; i < nums2.size(); i++) {
if(cnt.count(nums2[i])) {
mn = min(mn, nums2[i]);
};
num2 = min(nums2[i], num2);
}
if(mn < 10) return mn;
if(num1 < num2) {
return num1 * 10 + num2;
} else {
return num2 * 10 + num1;
}
}
1 : Function Declaration
int minNumber(vector<int>& nums1, vector<int>& nums2) {
The function starts by taking two input arrays, nums1 and nums2, which represent two lists of integers.
2 : Variable Initialization
int num1 = nums1[0];
The first element of nums1 is assigned to num1, which will hold the minimum value in the first array.
3 : Set Initialization
set<int> cnt;
A set 'cnt' is created to store unique values from nums1, helping with finding common elements between the two arrays.
4 : Variable Initialization
int mn = 10;
A variable 'mn' is initialized to 10, which is used to track the minimum value found from the common elements of nums1 and nums2.
5 : Looping Through Array 1
for(int i = 0; i < nums1.size(); i++) {
This loop iterates through all elements of nums1 to populate the set 'cnt' and update the minimum value of num1.
6 : Set Insertion
cnt.insert(nums1[i]);
Each element of nums1 is inserted into the set 'cnt' to ensure all elements are unique.
7 : Updating Minimum Value
num1 = min(nums1[i], num1);
The minimum value of nums1 is updated during each iteration of the loop.
8 : Variable Initialization
int num2 = nums2[0];
The first element of nums2 is assigned to num2, which will hold the minimum value in the second array.
9 : Looping Through Array 2
for(int i = 0; i < nums2.size(); i++) {
This loop iterates through all elements of nums2 and checks for common elements between nums1 and nums2.
10 : Checking for Common Elements
if(cnt.count(nums2[i])) {
This checks if the current element of nums2 exists in the set 'cnt' (i.e., it is a common element).
11 : Updating Minimum Value
mn = min(mn, nums2[i]);
If a common element is found, the minimum value 'mn' is updated with the smaller of the two values.
12 : Updating Minimum Value
num2 = min(nums2[i], num2);
The minimum value of nums2 is updated during each iteration of the loop.
13 : Returning the Result
if(mn < 10) return mn;
If a common element was found (mn < 10), return the smallest common element.
14 : Condition Check
if(num1 < num2) {
This checks if num1 is smaller than num2.
15 : Returning the Result
return num1 * 10 + num2;
If num1 is smaller, return the number formed by concatenating num1 and num2.
16 : Condition Check
} else {
Else condition if num1 is not smaller than num2.
17 : Returning the Result
return num2 * 10 + num1;
If num1 is not smaller than num2, return the number formed by concatenating num2 and num1.
Best Case: O(1)
Average Case: O(n)
Worst Case: O(n)
Description: In the worst case, we check all elements of both arrays, which requires O(n) time where n is the size of the arrays (at most 9).
Best Case: O(1)
Worst Case: O(n)
Description: We store sets for quick lookup, requiring O(n) space in the worst case, where n is the size of the arrays (at most 9).
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus