2540. Minimum Common Value

Time: O(m + n)

Space: O(1)

Intuition

Because both arrays are sorted in non-decreasing order, the smallest common value can be found without extra storage. Two pointers let us discard smaller values immediately: if nums1[i] is smaller, it can never match any earlier value in nums2, and vice versa.

Algorithm

1Initialise two pointers i = 0 and j = 0.
2While both pointers are inside their arrays:
3 If nums1[i] == nums2[j], return that value immediately.
4 If nums1[i] < nums2[j], increment i because nums1[i] is too small to match nums2[j] or anything before it.
5 Otherwise increment j for the symmetric reason.
6If one pointer reaches the end, no common value exists, so return -1.

Example Walkthrough

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

1.Compare 1 and 2: 1 is smaller, so move i to the next element.
2.Compare 2 and 2: they match, so 2 is the smallest common value.

Output: 2

Common Pitfalls

•This works only because both arrays are sorted; on unsorted arrays, pointer moves would skip valid matches.
•Return on the first match, not the last one, because the pointers advance in ascending order.
•Do not use nested loops here; they increase time complexity unnecessarily to O(m*n).

2540.cs

// Approach: Use two pointers because both arrays are already sorted.
// If nums1[i] is smaller, move i forward; if nums2[j] is smaller, move j forward.
// The first time both values match, that value is the minimum common element.
// Time: O(m + n) Space: O(1)

public class Solution
{
    public int GetCommon(int[] nums1, int[] nums2)
    {
        int i = 0; // nums1's index
        int j = 0; // nums2's index

        while (i < nums1.Length && j < nums2.Length)
        {
            if (nums1[i] == nums2[j])
                return nums1[i];
            if (nums1[i] < nums2[j])
                ++i;
            else
                ++j;
        }

        return -1;
    }
}

Was this solution helpful?