2605. Form Smallest Number From Two Digit Arrays
Problem Description
The task here involves finding the smallest number that comprises at least one digit from each of the two given arrays, nums1 and nums2. The arrays contain unique digits, meaning each digit from 0 to 9 appears at most once in each array. We are looking to build the smallest number possible using only one digit from each array, without repeating any digit.
To achieve the smallest number, we generally should start with the smallest digit from the two given arrays. However, if both arrays contain a common digit, we can use just this digit as it fulfills the criteria of containing at least one digit from each array while ensuring the number is as small as possible. If there are no common digits, we have to take the smallest digit from each array and combine them to form a two-digit number, carefully arranging them in an order that results in the smallest possible number.
Intuition
The solution is intuitive once we understand the problem's requirements. If there is a common digit, our job becomes very straightforward; we just output this digit. However, if there isn't, we need to create a two-digit number using the smallest digit from each array.
Solution 1: Enumeration
In this approach, we compare each digit from one array to every digit in the other array to check for common digits. If we find a common digit, we return it; if not, we proceed with concatenating the smallest digit from one array with the smallest from the other array. We ensure to test both possible concatenations and choose the smaller one.
Solution 2: Hash Table or Array + Enumeration
Using a hash table or an array allows us to keep track of which digits are present in each array more efficiently. We need a fixed-sized structure (since digits only go from 0 to 9), and we check each digit against this structure. The moment we find a common digit, we conclude the search and return it. If there are no common digits, we again proceed to find the smallest two digits and concatenate them in both possible ways, returning the smaller resulting number.
Solution 3: Bit Operation
This approach leverages the limited range of digits (1 to 9) and uses bit manipulation to effectively track which digits are present in each array. The main insight here is that each bit in a 10-bit binary number can represent the presence (1) or absence (0) of a corresponding digit. Using bit 'OR' operations, we can quickly build a bitmask for each array that reflects its content. We then perform a bit 'AND' operation to find any common digits. If we find none, we identify the position of the last 1 bit in each mask to find the smallest digits from each array, concatenate these digits in both possible orders and return the smallest of the two values.
How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).
Solution Approach
The solution implements the third approach, which leverages bit manipulation to efficiently determine the smallest number that contains at least one digit from each array (nums1 and nums2). Here's a breakdown of this approach:
-
Initializing Masks: We initialize two bitmask variables,
mask1andmask2, to zero. These will represent the presence of digits innums1andnums2, respectively. -
Building Bitmasks: We iterate through each number
xin bothnums1andnums2separately and update the corresponding masks using an 'OR' operation (|= 1 << x). The 'OR' operation ensures that the bit at the position corresponding to the digitxis set to1. -
Finding Common Digits: Once we have our bitmasks, we check for common digits by performing a bitwise 'AND' operation between
mask1andmask2(mask = mask1 & mask2). If any common digit exists,maskwill not be zero. The common digit can be found by the position of the last1inmask, which is calculated as(mask & -mask).bit_length() - 1. -
Extracting Smallest Non-Common Digits: If
maskis zero, it means there are no common digits. We find the position of the last1in both masksmask1andmask2to get the smallest digitsaandbfrom each array. We use the bitwise 'AND' operation with the two's complement of each bitmask to isolate the last1bit ((mask1 & -mask1).bit_length() - 1and(mask2 & -mask2).bit_length() - 1). -
Forming the Smallest Number: Depending on whether a common digit exists, the smallest number is either the position of the last
1inmaskor the minimum of two numbers created by concatenatingaandbin different orders (min(a * 10 + b, b * 10 + a)).
This bit manipulation method is very efficient because it reduces the problem of finding digits and comparing them to simple bitwise operations, which are performed quickly at the hardware level. Instead of needing to store and search through a hash table or array, this approach makes use of existing integer operations to encode the same information in a very compact space.
The space complexity of this algorithm is constant, O(1), because the bitmasks do not grow with the size of the input arrays. The time complexity is linear, O(m + n), where m and n are the lengths of nums1 and nums2, because we only need single passes through each array to build the bitmasks.
Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?
Example Walkthrough
Let's illustrate the solution approach using a small example:
Suppose we have two arrays: nums1 = [4, 3] and nums2 = [5, 1].
Initializing Masks:
- We start by initializing two bitmasks,
mask1andmask2, to zero (0).
Building Bitmasks:
- We iterate through
nums1, updatingmask1for each digit:- For digit
4, the binary representation of1 << 4is10000. Performingmask1 |= 10000results inmask1 = 10000. - For digit
3, the binary representation of1 << 3is01000. Performingmask1 |= 01000updatesmask1to11000.
- For digit
- Then, we iterate through
nums2, updatingmask2for each digit:- For digit
5, the binary representation of1 << 5is100000. Performingmask2 |= 100000results inmask2 = 100000. - For digit
1, the binary representation of1 << 1is00010. Performingmask2 |= 00010updatesmask2to100010.
- For digit
At this point, we have mask1 = 11000 and mask2 = 100010.
Finding Common Digits:
- We look for common digits by performing
mask = mask1 & mask2, resulting inmask = 000000. Since there are no common digits (mask = 0), we move on to extracting the smallest non-common digit from each array.
Extracting Smallest Non-Common Digits:
- The smallest digit in
nums1can be found by isolating the last1inmask1, which is00001000. We get its bit position using(mask1 & -mask1).bit_length() - 1. In this case,mask1 & -mask1equals00001000, whosebit_length()is4, but we subtract1for zero-based indexing, soa = 3. - Similarly, for
mask2equaling100010,(mask2 & -mask2).bit_length() - 1returns the bit position of the last1, which is1in this case. So,b = 1.
Forming the Smallest Number:
- Since there's no common digit, we create two possible numbers by combining
aandb:a * 10 + b = 31andb * 10 + a = 13. The smallest of these two is13.
So, the smallest number comprising at least one digit from each array using the bit operation method is the number 13.
This example demonstrates how the bit manipulation method outlined in the solution approach can be applied to efficiently solve the given problem.
Solution Implementation
1class Solution:
2 def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
3 # Initialize two bit masks to represent the numbers present in nums1 and nums2.
4 mask1 = mask2 = 0
5
6 # Iterate over the first list and update the mask1 to track the numbers.
7 for num in nums1:
8 mask1 |= 1 << num
9
10 # Iterate over the second list and update the mask2 to track the numbers.
11 for num in nums2:
12 mask2 |= 1 << num
13
14 # Create a mask to find common elements by applying bitwise AND on mask1 and mask2.
15 common_mask = mask1 & mask2
16
17 # If there is a common number, return the smallest one.
18 if common_mask:
19 # Find the smallest number by isolating the lowest set bit and calculating its index.
20 return (common_mask & -common_mask).bit_length() - 1
21
22 # If no common number is found, find the smallest number from each list.
23 # Find the lowest set bit for each mask to get the smallest number from each list.
24 smallest_num1 = (mask1 & -mask1).bit_length() - 1
25 smallest_num2 = (mask2 & -mask2).bit_length() - 1
26
27 # Compute the smallest two-digit number using the smallest elements from both lists.
28 # Because we need the lexicographically smallest number, we calculate both combinations.
29 smallest_combination = min(smallest_num1 * 10 + smallest_num2, smallest_num2 * 10 + smallest_num1)
30
31 # Return the smallest two-digit number.
32 return smallest_combination
331class Solution {
2
3 public int minNumber(int[] nums1, int[] nums2) {
4 // Initialize bit masks for both arrays to track the numbers present
5 int maskNums1 = 0, maskNums2 = 0;
6
7 // Iterate through nums1 and set corresponding bits in the mask for nums1
8 for (int num : nums1) {
9 maskNums1 |= 1 << num;
10 }
11
12 // Iterate through nums2 and set corresponding bits in the mask for nums2
13 for (int num : nums2) {
14 maskNums2 |= 1 << num;
15 }
16
17 // Calculate the bitwise AND of both masks to find common numbers
18 int commonMask = maskNums1 & maskNums2;
19
20 // If there is a common number, return the smallest one
21 if (commonMask != 0) {
22 return Integer.numberOfTrailingZeros(commonMask);
23 }
24
25 // If there are no common numbers, find the smallest numbers in each array
26 int smallestNums1 = Integer.numberOfTrailingZeros(maskNums1);
27 int smallestNums2 = Integer.numberOfTrailingZeros(maskNums2);
28
29 // Calculate the minimum number by concatenating the smallest numbers from both arrays
30 // in both possible orders and return the smallest result
31 return Math.min(smallestNums1 * 10 + smallestNums2, smallestNums2 * 10 + smallestNums1);
32 }
33}
341#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Function to find the minimum number by analyzing two vectors
7 int minNumber(std::vector<int>& nums1, std::vector<int>& nums2) {
8 int mask1 = 0; // Binary mask for the first vector
9 int mask2 = 0; // Binary mask for the second vector
10
11 // Populate the binary mask for nums1
12 for (int num : nums1) {
13 mask1 |= 1 << num;
14 }
15
16 // Populate the binary mask for nums2
17 for (int num : nums2) {
18 mask2 |= 1 << num;
19 }
20
21 // Intersection mask to find common elements
22 int commonMask = mask1 & mask2;
23
24 if (commonMask) {
25 // If there's a common element, return the smallest one
26 return __builtin_ctz(commonMask);
27 }
28
29 // If there are no common elements, find the smallest elements in each vector
30 int smallestNums1 = __builtin_ctz(mask1);
31 int smallestNums2 = __builtin_ctz(mask2);
32
33 // Construct and return the minimum of the two possible two-digit numbers
34 return std::min(smallestNums1 * 10 + smallestNums2, smallestNums2 * 10 + smallestNums1);
35 }
36};
371// Function to find the minimum number that can be formed from the elements of two arrays.
2function minNumber(nums1: number[], nums2: number[]): number {
3 let bitMask1: number = 0;
4 let bitMask2: number = 0;
5
6 // Create a bitmask to represent the presence of numbers in nums1.
7 for (const num of nums1) {
8 bitMask1 |= 1 << num;
9 }
10
11 // Create a bitmask to represent the presence of numbers in nums2.
12 for (const num of nums2) {
13 bitMask2 |= 1 << num;
14 }
15
16 // Calculate the common bits between both masks.
17 const commonBitMask = bitMask1 & bitMask2;
18
19 // If there's a common number between nums1 and nums2, return its bit position.
20 if (commonBitMask !== 0) {
21 return numberOfTrailingZeros(commonBitMask);
22 }
23
24 // Find the smallest number from each array.
25 const smallestNumInNums1 = numberOfTrailingZeros(bitMask1);
26 const smallestNumInNums2 = numberOfTrailingZeros(bitMask2);
27
28 // Return the smallest two-digit number that can be formed from the inputs.
29 return Math.min(smallestNumInNums1 * 10 + smallestNumInNums2, smallestNumInNums2 * 10 + smallestNumInNums1);
30}
31
32// Function to count the number of trailing zeros in the binary representation of a number.
33function numberOfTrailingZeros(i: number): number {
34 if (i === 0) {
35 return 32; // Special case where i is 0.
36 }
37
38 let position = 31;
39 let temp = 0;
40
41 // For each segment, shift `i` left and decrease position if the result is non-zero.
42 temp = i << 16;
43 if (temp !== 0) {
44 position -= 16;
45 i = temp;
46 }
47 temp = i << 8;
48 if (temp !== 0) {
49 position -= 8;
50 i = temp;
51 }
52 temp = i << 4;
53 if (temp !== 0) {
54 position -= 4;
55 i = temp;
56 }
57 temp = i << 2;
58 if (temp !== 0) {
59 position -= 2;
60 i = temp;
61 }
62
63 // Return the number of trailing zeros by examining the final bit position.
64 return position - ((i << 1) >>> 31);
65}
66What's the output of running the following function using input 56?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
271private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
301const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30Time and Space Complexity
The time complexity of the code is O(m + n) where m is the length of nums1 and n is the length of nums2. This is because the code iterates through each of the two lists exactly once to create two bitmasks. The bitwise OR operations inside the loops take constant time per element.
After creating the bitmasks, the subsequent operations involving bitwise AND and finding the rightmost set bit also execute in constant time, as they are not dependent on the size of the input but instead on the fixed size of an integer (typically 32 or 64 bits in modern architectures).
The space complexity of the code is O(1). This constant space usage comes from the fact that no matter the size of the input lists, the code only uses a fixed number of integer variables (mask1, mask2, mask, a, and b). These variables do not scale with the input size, resulting in constant space consumption.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
121import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
181function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.