#2540

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Minimum Common Value

Find the smallest integer appearing in both sorted arrays efficiently using array scanning and hash-based lookup techniques.

array hash table two pointers binary search

Problem Statement

Given two non-decreasing integer arrays, nums1 and nums2, determine the smallest integer that is present in both arrays. If no such integer exists, return -1. Each array may contain duplicates, but only the minimum common value matters.

For example, given nums1 = [1,2,3,6] and nums2 = [2,3,4,5], the integers 2 and 3 appear in both arrays. The smallest among them is 2, so the function should return 2. Arrays can be large, so an efficient approach is required.

Examples

Example 1

Input: nums1 = [1,2,3], nums2 = [2,4]

Output: 2

The smallest element common to both arrays is 2, so we return 2.

Example 2

Input: nums1 = [1,2,3,6], nums2 = [2,3,4,5]

Output: 2

There are two common elements in the array 2 and 3 out of which 2 is the smallest, so 2 is returned.

Constraints

1 <= nums1.length, nums2.length <= 105
1 <= nums1[i], nums2[j] <= 109
Both nums1 and nums2 are sorted in non-decreasing order.

Solution Approach

Use a Hash Set for Quick Lookup

Insert all elements from nums1 into a hash set. Then iterate through nums2 and return the first element found in the set. This method ensures constant-time existence checks and directly finds the minimum common value.

Two-Pointer Scan on Sorted Arrays

Initialize two pointers at the start of nums1 and nums2. Move the pointer of the smaller value forward until both point to the same value. The first match is the minimum common value. This avoids extra space while leveraging the sorted property.

Binary Search Alternative

For each element in the smaller array, perform a binary search in the larger array. The first element found in both arrays is the minimum common value. This approach trades scanning simplicity for log-time search efficiency.

Complexity Analysis

Metric	Value
Time	O(n \log m)
Space	O(1)

Time complexity is O(n log m) when using binary search or O(n + m) for a hash set or two-pointer method. Space complexity is O(1) for two-pointer scan or O(n) if a set is used.

What Interviewers Usually Probe

Do you recognize the sorted array property that allows two-pointer optimization?
Can you identify when a hash set reduces lookup time versus scanning?
How do you handle arrays with duplicates without affecting the minimum common value?

Common Pitfalls or Variants

Common pitfalls

Returning the first duplicate match instead of the minimum value.
Using nested loops leading to O(n*m) time instead of O(n + m) or O(n log m).
Neglecting edge cases when one array has no common elements.

Follow-up variants

Find all common values instead of only the minimum.
Return the maximum common value between two arrays.
Handle arrays that are not sorted and compare trade-offs in approach.

FAQ

What is the best method for finding the minimum common value?

Using a hash set to check existence or a two-pointer scan on sorted arrays ensures the minimum common value is found efficiently.

Can duplicates affect the minimum common value result?

No, duplicates do not change the result; only the smallest integer present in both arrays matters.

How does the two-pointer approach work?

Pointers start at the beginning of each sorted array, advancing the smaller value until a match is found, which is the minimum common value.

Is binary search faster than a hash set in this problem?

Binary search is O(n log m) and can be efficient when one array is much smaller, but a hash set or two-pointer scan is often simpler and faster in practice.

Does GhostInterview guide me through array scanning plus hash lookup patterns?

Yes, it provides detailed step guidance, highlights pitfalls, and ensures your solution handles edge cases effectively.

terminal

Solution

Solution 1: Two Pointers

Traverse the two arrays. If the elements pointed to by the two pointers are equal, return that element. If the elements pointed to by the two pointers are not equal, move the pointer pointing to the smaller element to the right by one bit until an equal element is found or the array is traversed.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        i = j = 0
        m, n = len(nums1), len(nums2)
        while i < m and j < n:
            if nums1[i] == nums2[j]:
                return nums1[i]
            if nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return -1

Solution 2

#### Rust

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        i = j = 0
        m, n = len(nums1), len(nums2)
        while i < m and j < n:
            if nums1[i] == nums2[j]:
                return nums1[i]
            if nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return -1

Continue Practicing

#2856 minimum array length after pair removals #3186 maximum total damage with spell casting #1782 count pairs of nodes