2540. Minimum Common Value

題目 / Problem

中文： 給定兩個整數陣列 nums1 和 nums2，皆按非遞減順序排序。請回傳兩個陣列中最小的共同整數。如果沒有共同的整數，回傳 -1。

「共同」的定義：某個整數在兩個陣列中至少各出現一次。

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

A value is "common" if it appears at least once in each array.

Constraints / 限制： - 1 <= nums1.length, nums2.length <= 10^5 - 1 <= nums1[i], nums2[j] <= 10^9 - Both arrays are sorted in non-decreasing order.

Example / 範例：

Input:  nums1 = [1,2,3], nums2 = [2,4]
Output: 2
Explanation: 2 出現在兩個陣列中，且是最小的共同值。

名詞解釋 / Glossary

Sorted in non-decreasing order / 非遞減排序： 陣列中每個元素都 ≥ 前一個元素（允許相等）。例如 [1,2,2,5]。This means each element is ≥ the previous one (duplicates allowed).
Two pointers / 雙指針： 用兩個索引變數同時掃描一個或多個陣列的技巧。對於兩個已排序陣列，可以在 O(n+m) 時間內完成比對。A technique where two index variables walk through arrays simultaneously; on sorted data it often replaces nested loops with a single O(n+m) pass.
Hash set / 雜湊集合： 一種資料結構，可以在平均 O(1) 時間內判斷某個元素是否存在。在 C++ 中是 unordered_set。A data structure that supports average-O(1) membership tests; unordered_set in C++.
Time complexity / 時間複雜度： 演算法執行時間隨輸入規模成長的數量級。常用 Big-O 記號表示，例如 O(n) 表示與輸入大小成正比。Order-of-growth of running time as input size grows, written in Big-O notation.
Pointer / 指標 (C)： 在 C 中，函式參數 int* nums1 表示一個指向整數陣列開頭的記憶體位址；nums1[i] 等同於 *(nums1+i)。In C, int* nums1 is the memory address of the array's first element; nums1[i] is array indexing.

思路

中文： 最直覺的「暴力解」是：對 nums1 中的每個數，掃描整個 nums2 看是否出現，找到就記錄。這需要 O(n·m) 的時間，當兩個陣列都有 10⁵ 個元素時就是 10¹⁰ 次比較，肯定會超時。

關鍵的觀察是：兩個陣列都已經排序好了。這是一個非常強的條件，意味著我們可以用「雙指針」的技巧，只用一次線性掃描就解決問題。設 i 指向 nums1 的開頭，j 指向 nums2 的開頭，每一步比較 nums1[i] 和 nums2[j]： - 如果相等，就找到了最小的共同值（因為我們是從小往大走的，第一次相等就是最小的），直接回傳。 - 如果 nums1[i] < nums2[j]，那麼 nums1[i] 不可能再出現在 nums2 中（nums2 後面只會更大），所以 i++ 跳過它。 - 反之，j++。

迴圈結束都沒找到就回傳 -1。這個方法的正確性來自於「排序」這個不變式（invariant）：每次我們丟棄的元素，已經被證明不可能是答案。時間複雜度 O(n+m)，空間 O(1)。

另一個選擇是把 nums2 放進雜湊集合，然後遍歷 nums1 查詢；時間也是 O(n+m) 平均，但需要 O(m) 額外空間，且常數較大。對這題雙指針更乾淨。

English: The brute force approach checks every element of nums1 against every element of nums2, which is O(n·m). With both arrays up to 10⁵ that's 10¹⁰ comparisons — far too slow.

The crucial observation: both arrays are already sorted. This lets us use the two-pointer technique to solve it in a single linear pass. Put i at the start of nums1 and j at the start of nums2. At each step, compare nums1[i] and nums2[j]: - If they're equal, we've found a common value. Since we scan from small to large, the first match is the smallest — return it immediately. - If nums1[i] < nums2[j], then nums1[i] can never appear in nums2 (every remaining element of nums2 is ≥ nums2[j] > nums1[i]), so advance i. - Otherwise, advance j.

If either pointer runs off the end, return -1. Correctness rests on the sorted-order invariant: every value we discard is provably not a candidate. The runtime is O(n+m) and space is O(1).

An alternative is to dump nums2 into a hash set and scan nums1. Same average time but O(m) extra space — two pointers is cleaner here.

逐步走查 / Walkthrough

Trace with nums1 = [1,2,3], nums2 = [2,4]. Initially i = 0, j = 0.

Step	`i`	`j`	`nums1[i]`	`nums2[j]`	Comparison	Action
1	0	0	1	2	`1 < 2`	`nums1[0]=1` 不在 `nums2` 中；`i++` → `i=1`
2	1	0	2	2	`2 == 2`	找到共同值 → 回傳 `2` ✓

只用了兩步就結束。注意第一步丟棄 1 是安全的：nums2 從 2 開始且非遞減，永遠不會再出現 1。

Only two iterations were needed. The discard of 1 in step 1 is safe because nums2 starts at 2 and never decreases — 1 cannot appear later.

Solution — C

/*
 * Algorithm: Two pointers on two sorted arrays.
 * 演算法：對兩個已排序陣列使用雙指針。
 * Walk i through nums1 and j through nums2; on equal values return the value
 * (it must be the smallest because both arrays are sorted ascending). Otherwise
 * advance whichever pointer points to the smaller value.
 */

int getCommon(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    // i, j 是兩個指針，分別指向 nums1 和 nums2 目前要比較的位置
    // i and j are the two pointers, one for each array, both starting at index 0
    int i = 0, j = 0;

    // 當兩個指針都還在陣列範圍內時繼續循環
    // Loop while neither pointer has walked off the end of its array
    while (i < nums1Size && j < nums2Size) {
        // 取出當前兩個位置的值，方便比較與閱讀
        // Cache the two current values for readability
        int a = nums1[i];   // nums1[i] 等同於 *(nums1+i) / array indexing in C
        int b = nums2[j];

        if (a == b) {
            // 第一次相等就是最小的共同值（因為兩陣列都從小到大）
            // First equality is the minimum common value (both arrays are ascending)
            return a;
        } else if (a < b) {
            // a 比 b 小：a 不可能出現在 nums2 後面（nums2 只會更大），跳過 a
            // a < b: a cannot appear later in nums2 (which only grows), so skip a
            i++;
        } else {
            // 對稱情況：b 比較小，跳過 b
            // Symmetric case: b is smaller, advance j
            j++;
        }
    }

    // 某一個指針已到底而仍未找到共同值，表示沒有共同元素
    // One array exhausted without a match — no common value exists
    return -1;
}

Solution — C++

/*
 * Algorithm: Two pointers on two sorted vectors.
 * 演算法：對兩個已排序的 vector 使用雙指針，O(n+m) 時間、O(1) 空間。
 * Identical logic to the C version, written in idiomatic C++.
 */

class Solution {
public:
    // vector<int>& 是「對 vector 的參考」，避免複製整個陣列（更快）
    // vector<int>& is a reference to the vector — avoids copying the whole array
    int getCommon(vector<int>& nums1, vector<int>& nums2) {
        // size_t 是 vector::size() 的回傳型別（非負整數）
        // size_t is the unsigned integer type returned by vector::size()
        size_t i = 0, j = 0;

        // .size() 回傳元素個數；只要兩邊都還有元素就繼續
        // .size() returns element count; continue while both have elements left
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i] == nums2[j]) {
                // 找到第一個相等值，因為從小到大掃描，這就是最小共同值
                // First equal pair is the minimum common value (ascending scan)
                return nums1[i];
            }
            // 三元判斷哪一邊比較小，將該邊的指針前進
            // Advance the pointer that points to the smaller value
            if (nums1[i] < nums2[j]) {
                ++i;   // 前綴 ++ 比後綴稍微高效（對 int 沒差，但是好習慣）
                       // Pre-increment is a stylistic habit in C++
            } else {
                ++j;
            }
        }

        // 沒找到共同值 / no common value found
        return -1;
    }
};

複雜度 / Complexity

Time: O(n + m) — 每次迴圈至少有一個指針會前進一步，兩個指針最多分別走 n 和 m 步，所以總步數最多 n+m。Each iteration advances at least one pointer; together they can advance a total of at most n+m steps before one array is exhausted. n = nums1.length, m = nums2.length.
Space: O(1) — 只使用了固定數量的指針變數，不隨輸入大小成長。We only use a constant number of integer variables (the two pointers); no extra data structures.

Pitfalls & Edge Cases

沒有共同元素 / No common element: 必須回傳 -1，不是 0 或拋例外。題目保證元素 ≥ 1，所以 -1 是安全的哨兵值。Must return -1, not 0. Since values are guaranteed ≥ 1, -1 is a safe sentinel.
重複元素 / Duplicates: 兩個陣列都可能有重複值（例如 [2,2,3]），但我們只關心「最小」共同值，第一次相等就回傳即可，重複不影響正確性。Duplicates are allowed; returning at the first match still yields the minimum.
誤用無序的雜湊集合方法時忘了取最小值 / Hash-set pitfall: 如果用雜湊集合，遍歷 nums1 時要記得只取最小的命中（或從小到大遍歷後立即 return）。雙指針天然避開這個陷阱。If you use a hash set, remember to track the minimum match (or iterate nums1 in order and return on first hit) — two pointers sidesteps this.
指針越界 / Pointer out-of-bounds: while 條件 i < nums1Size && j < nums2Size 必須同時檢查兩個指針，少寫一個就會讀到非法記憶體。Both bounds must be in the loop condition; omitting either causes an out-of-bounds read.
整數範圍 / Integer range: 元素最大 10⁹，仍在 32-bit int 範圍內（~2.1×10⁹），不會溢位。Values fit in 32-bit int; no overflow concern here.