algoadvance

Leetcode 2540. Minimum Common Value

Problem Statement

Given two integer arrays nums1 and nums2 sorted in non-decreasing order, return the minimum integer common to both arrays. If there is no common integer amongst nums1 and nums2, return -1.

Clarifying Questions

  1. What are the constraints of the input arrays?
    • The lengths of nums1 and nums2 can be up to 10^5.
    • The elements of nums1 and nums2 can range from 1 to 10^9.
  2. Can the arrays contain duplicate elements?
    • Yes, the arrays can contain duplicate elements, but since we are looking for the minimum integer common to both arrays, duplicates do not affect the minimum value found.
  3. What should be returned if no common value exists?
    • Return -1 if there is no common value.
  4. Are the arrays always given in sorted order?
    • Yes, both arrays are given sorted in non-decreasing order.

Strategy

Considering that both arrays are sorted, we can efficiently find the minimum common value using a two-pointer technique.

  1. Start with two pointers, each pointing to the beginning of nums1 and nums2.
  2. Compare the elements at both pointers.
    • If they are equal, this is a common element. It is the smallest because the arrays are sorted, so we return this element immediately.
    • If the element in nums1 is smaller, increment the pointer in nums1 to try and find a larger element that might match the current element in nums2.
    • If the element in nums2 is smaller, increment the pointer in nums2 to try and find a larger element that might match the current element in nums1.
  3. If the end of any array is reached without finding a common element, return -1.

Time Complexity

Code

Here’s the Java implementation of the solution:

public class MinimumCommonValue {
    public int getCommon(int[] nums1, int[] nums2) {
        int pointer1 = 0;
        int pointer2 = 0;
        
        while (pointer1 < nums1.length && pointer2 < nums2.length) {
            if (nums1[index1] == nums2[index2]) {
                return nums1[index1];
            } else if (nums1[index1] < nums2[index2]) {
                pointer1++;
            } else {
                pointer2++;
            }
        }
        
        return -1; // No common element found
    }

    public static void main(String[] args) {
        MinimumCommonValue sol = new MinimumCommonValue();
        int[] nums1 = {1, 2, 3, 4, 5};
        int[] nums2 = {3, 5, 7, 9};
        System.out.println(sol.getCommon(nums1, nums2)); // Output: 3
        
        int[] nums1_2 = {6, 7, 8, 9};
        int[] nums2_2 = {1, 2, 3, 10};
        System.out.println(sol.getCommon(nums1_2, nums2_2)); // Output: -1
    }
}

This code defines a method getCommon which implements the above strategy using two pointers to find the minimum common value or determine that no common element exists. The main method provides some sample inputs to test the function.

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