algoadvance

Leetcode 2605. Form Smallest Number From Two Digit Arrays

Problem Statement

LeetCode Problem 2605: Form Smallest Number From Two Digit Arrays

You are given two arrays of digits nums1 and nums2. You need to form the smallest possible number by picking one digit from nums1 and one digit from nums2.

Clarifying Questions

  1. Input Constraints:
    • Are the arrays guaranteed to have at least one element each?
      • Yes, the arrays will not be empty.
    • What is the possible range of the digits within the arrays?
      • The digits will range from 1 to 9.
  2. Return Value:
    • Should the function return the smallest possible number as an integer?
      • Yes, the function should return an integer.

Strategy

  1. Identify Common Digits:
    • First, check if there is any common digit between the two arrays. If a common digit exists, the smallest common digit will form the smallest number.
  2. Form from Different Digits:
    • If no common digit exists, form the smallest number by picking the smallest digit from each array and concatenating them. For example, if the smallest digit of nums1 is a and the smallest of nums2 is b, the numbers to consider are 10 * a + b and 10 * b + a. Return the smaller of these two numbers.

Code

#include <algorithm>
#include <unordered_set>
#include <vector>
#include <iostream>

class Solution {
public:
    int minNumber(std::vector<int>& nums1, std::vector<int>& nums2) {
        // Sort both arrays to find the smallest elements quickly
        std::sort(nums1.begin(), nums1.end());
        std::sort(nums2.begin(), nums2.end());

        // Step 1: Check if there's a common digit
        std::unordered_set<int> numSet(nums1.begin(), nums1.end());
        for (int num : nums2) {
            if (numSet.find(num) != numSet.end()) {
                // Smallest common element forms the smallest number
                return num;
            }
        }

        // Step 2: No common digits, combine the smallest elements
        int smallestNum1 = nums1.front(); // Smallest element in nums1
        int smallestNum2 = nums2.front(); // Smallest element in nums2

        // Create two possible numbers and return the smallest one
        int num1 = smallestNum1 * 10 + smallestNum2;
        int num2 = smallestNum2 * 10 + smallestNum1;

        return std::min(num1, num2);
    }
};

int main() {
    Solution solution;
    std::vector<int> nums1 = {4, 1, 3};
    std::vector<int> nums2 = {5, 7, 3};
    std::cout << solution.minNumber(nums1, nums2) << std::endl; // Output: 3

    std::vector<int> nums1_case2 = {4, 1, 3};
    std::vector<int> nums2_case2 = {5, 7, 2};
    std::cout << solution.minNumber(nums1_case2, nums2_case2) << std::endl; // Output: 12

    return 0;
}

Time Complexity

  1. Sorting:
    • Sorting nums1 takes (O(n \log n)), where (n) is the length of nums1.
    • Sorting nums2 takes (O(m \log m)), where (m) is the length of nums2.
  2. Set Operations:
    • Inserting elements of nums1 into a set takes (O(n)).
    • Checking presence of elements in a set for nums2 takes (O(m)).

Combining these, the overall time complexity is (O(n \log n + m \log m)).

Space Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI