algoadvance

Leetcode 2605. Form Smallest Number From Two Digit Arrays

Problem Statement

You have two arrays of digits, nums1 and nums2. Return the smallest number that contains at least one digit from each of the arrays.

Clarifying Questions

  1. What are the constraints of the problem?
    • The arrays nums1 and nums2 will each contain at least one digit.
    • Each array will contain digits from 0 to 9.
    • The arrays may contain duplicate elements.
  2. What is the output format?
    • The output should be an integer representing the smallest number that can be formed using at least one digit from each of the arrays.
  3. Are there any restrictions on the size of the arrays?
    • No explicit restrictions on the size of the arrays are provided, so we assume they can be reasonably large but within practical limits for the problem context.

Strategy

To solve this problem, we need to consider the following steps:

  1. Identify common digits: Check for any common digits between the two arrays. If there is any common digit, the smallest one would be the smallest possible number.
  2. Combine digits: If there are no common digits, combine one digit from each array to form the smallest possible two-digit number.

Steps:

  1. Use a boolean array of size 10 to mark the presence of digits in both arrays.
  2. Find the smallest common digit if it exists.
  3. If no common digit exists, find the smallest digit in nums1 and the smallest digit in nums2 and combine them in both possible orders (e.g., for digits a and b, consider ab and ba), then return the smaller of the two combinations.

Code

Here’s how you can implement the solution in Java:

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int formSmallestNumber(int[] nums1, int[] nums2) {
        boolean[] digits1 = new boolean[10];
        boolean[] digits2 = new boolean[10];
        
        // Mark the digits present in nums1
        for (int num : nums1) {
            digits1[num] = true;
        }

        // Mark the digits present in nums2
        for (int num : nums2) {
            digits2[num] = true;
        }

        // Find the smallest common digit if present
        for (int i = 0; i < 10; i++) {
            if (digits1[i] && digits2[i]) {
                return i;
            }
        }

        // Find the smallest digit in nums1
        int min1 = Integer.MAX_VALUE;
        for (int num : nums1) {
            if (num < min1) {
                min1 = num;
            }
        }

        // Find the smallest digit in nums2
        int min2 = Integer.MAX_VALUE;
        for (int num : nums2) {
            if (num < min2) {
                min2 = num;
            }
        }

        // Combine the digits to form the smallest number
        int combined1 = min1 * 10 + min2;
        int combined2 = min2 * 10 + min1;

        // Return the smallest combination
        return Math.min(combined1, combined2);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {4, 1, 3};
        int[] nums2 = {5, 7};
        System.out.println(solution.formSmallestNumber(nums1, nums2));  // Output: 15
    }
}

Time Complexity

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