LeetCode 2540 - Minimum Common Value

LeetCode Problem 2540

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Two Pointers, Binary Search

Solution

Problem Understanding

The problem gives us two integer arrays, nums1 and nums2, and both arrays are already sorted in non-decreasing order. Our task is to find the smallest integer that appears in both arrays. If there is no value shared between the two arrays, we must return -1.

In other words, we need to identify the minimum common element between the two sorted lists. A value only needs to appear at least once in each array to qualify as common. Duplicate occurrences do not matter beyond confirming the presence of the value.

For example, if:

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

the number 2 appears in both arrays, and since it is the smallest such value, the answer is 2.

The constraints are important:

• Each array can contain up to 10^5 elements.
• Values can be as large as 10^9.
• Both arrays are already sorted.

These constraints immediately tell us that a naive nested loop solution may become too slow. A quadratic solution with complexity O(n × m) could require up to 10^10 comparisons in the worst case, which is far beyond acceptable limits.

The fact that both arrays are sorted is the key observation. Sorted order often allows efficient techniques such as two pointers or binary search.

There are several important edge cases to keep in mind:

• The arrays may have no common value at all.
• One array may contain duplicates.
• The smallest common value may appear very early.
• The common value may appear near the end of both arrays.
• Arrays may contain only one element each.

The problem guarantees that both arrays are non-empty and sorted, so we do not need to handle null or unsorted input.

Approaches

Brute Force Approach

The most direct solution is to compare every element in nums1 with every element in nums2.

For each value in the first array, we scan the second array looking for a match. Whenever we find a common value, we keep track of the minimum one encountered.

This approach is correct because it exhaustively checks all possible pairs of elements. If a common value exists, it will eventually be found.

However, this method is extremely inefficient for large inputs. If both arrays contain 10^5 elements, the algorithm could perform up to 10^10 comparisons in the worst case.

Because of this, the brute force solution is too slow for the given constraints.

Optimal Approach, Two Pointers

The arrays are already sorted, which allows us to process them efficiently using two pointers.

We maintain one pointer for each array:

• i points into nums1
• j points into nums2

At each step:

• If nums1[i] == nums2[j], we found the smallest common value and can return it immediately.
• If nums1[i] < nums2[j], then nums1[i] cannot possibly match any future value in nums2, because all future values in nums2 are greater or equal. Therefore, we move pointer i forward.
• If nums1[i] > nums2[j], we move pointer j forward for the same reason.

Because each pointer only moves forward, every element is processed at most once.

This produces a linear time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(1)	Compare every pair of elements
Optimal	O(n + m)	O(1)	Uses two pointers on sorted arrays

Algorithm Walkthrough

1. Initialize two pointers, i and j, both starting at 0.
2. Continue looping while both pointers remain within their respective array bounds.
3. Compare the current values:

• nums1[i]
• nums2[j]

4. If the two values are equal, return that value immediately.

Since both arrays are sorted, this is guaranteed to be the smallest common value. 5. If nums1[i] is smaller than nums2[j], increment i.

This works because the smaller value cannot match any later element in the second array. 6. Otherwise, increment j.

The smaller value in the second array cannot match any later element in the first array. 7. If the loop finishes without finding a match, return -1.

Why it works

The correctness comes from the sorted property of both arrays.

At every step, the algorithm discards the smaller value because it cannot possibly appear later in the other array. Since pointers only move forward, no potential match is skipped.

The first equality encountered must be the minimum common value because all smaller values have already been eliminated.

Python Solution

from typing import List

class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        i = 0
        j = 0

        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                return nums1[i]

            if nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1

        return -1

The implementation begins by initializing two pointers, one for each array.

The while loop continues as long as both pointers remain valid. Inside the loop, the current elements are compared.

If the values match, the algorithm immediately returns the value because the arrays are sorted and this is guaranteed to be the smallest common element.

If the current value in nums1 is smaller, the pointer i advances. Otherwise, the pointer j advances.

Eventually, either a common value is found or one pointer reaches the end of its array. If no match exists, the function returns -1.

Go Solution

func getCommon(nums1 []int, nums2 []int) int {
    i := 0
    j := 0

    for i < len(nums1) && j < len(nums2) {
        if nums1[i] == nums2[j] {
            return nums1[i]
        }

        if nums1[i] < nums2[j] {
            i++
        } else {
            j++
        }
    }

    return -1
}

The Go implementation follows exactly the same logic as the Python version.

Slices are used directly, and indices are managed manually with integer variables. Since the constraints fit comfortably within Go's integer range, there are no overflow concerns.

Go does not distinguish between empty and nil slices for length checks in this context, so the implementation works correctly for all valid inputs.

Worked Examples

Example 1

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

Initial state:

i	nums1[i]	j	nums2[j]	Action
0	1	0	2	1 < 2, increment i

Next iteration:

i	nums1[i]	j	nums2[j]	Action
1	2	0	2	Match found, return 2

Final answer:

2

Example 2

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

Initial iteration:

i	nums1[i]	j	nums2[j]	Action
0	1	0	2	1 < 2, increment i

Second iteration:

i	nums1[i]	j	nums2[j]	Action
1	2	0	2	Match found, return 2

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each pointer moves through its array at most once
Space	O(1)	Only a few variables are used

The algorithm is linear because every iteration advances either i or j. No pointer ever moves backward, so the total number of iterations cannot exceed len(nums1) + len(nums2).

The space complexity is constant because no extra data structures are allocated.

Test Cases

sol = Solution()

assert sol.getCommon([1,2,3], [2,4]) == 2  # basic example
assert sol.getCommon([1,2,3,6], [2,3,4,5]) == 2  # multiple common values
assert sol.getCommon([1,2,3], [4,5,6]) == -1  # no common value
assert sol.getCommon([1], [1]) == 1  # single element arrays with match
assert sol.getCommon([1], [2]) == -1  # single element arrays without match
assert sol.getCommon([1,1,2,2], [2,2,3]) == 2  # duplicates in arrays
assert sol.getCommon([5,6,7], [1,2,3,5]) == 5  # common value near end
assert sol.getCommon([1,2,3], [1,2,3]) == 1  # identical arrays
assert sol.getCommon([1000000000], [1000000000]) == 1000000000  # large values
assert sol.getCommon([1,3,5,7], [2,4,6,8]) == -1  # interleaved but disjoint

Test	Why
[1,2,3] and [2,4]	Verifies basic matching
[1,2,3,6] and [2,3,4,5]	Verifies smallest common value is returned
[1,2,3] and [4,5,6]	Verifies no-match handling
[1] and [1]	Tests smallest valid input with match
[1] and [2]	Tests smallest valid input without match
Arrays with duplicates	Ensures duplicates do not break logic
Match near end	Verifies pointers continue correctly
Identical arrays	Ensures earliest common value returned
Large integer values	Verifies handling of upper numeric range
Interleaved disjoint arrays	Ensures correct pointer movement

Edge Cases

One important edge case occurs when the arrays share no common value at all. A careless implementation might accidentally return an incorrect value or run past array boundaries. The two pointer solution handles this safely because the loop terminates as soon as one pointer reaches the end of its array, after which -1 is returned.

Another important case involves duplicate values. For example:

nums1 = [1,1,2,2]
nums2 = [2,2,3]

The algorithm still works because duplicates do not affect pointer correctness. The pointers continue advancing until a match is found. The first shared value encountered is still the minimum common value.

A third edge case occurs when the common value appears very late in both arrays. For example:

nums1 = [1,2,3,100]
nums2 = [50,60,70,100]

The implementation correctly advances pointers through many non-matching values without revisiting earlier elements. Since each pointer only moves forward, the runtime remains linear.

Another subtle edge case is when the arrays are identical. In that situation, the first elements immediately match, and the algorithm returns the correct minimum value without unnecessary processing.