---
# System prepended metadata

title: 2540. Minimum Common Value
tags: [two pointers, leetcode, binary search, hash table]

---

# 資訊

:::info
- Question: 2540. Minimum Common Value
- From: Leetcode Daily Challenge 2024.03.09
- Difficulty: Easy
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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`.

Note that an integer is said to be common to `nums1` and `nums2` if both arrays have at least one occurrence of that integer.

> Example 1:
:::success
- Input: `nums1 = [1,2,3]`, `nums2 = [2,4]`
- Output: 2
- Explanation: The smallest element common to both arrays is 2, so we return 2.
:::

> Example 2:
:::success
- Input: `nums1 = [1,2,3,6]`, `nums2 = [2,3,4,5]`
- Output: 2
- Explanation: There are two common elements in the array 2 and 3 out of which 2 is the smallest, so 2 is returned.
:::

> Constraints:
:::success
- 1 <= `nums1.length`, `nums2.length` <= $10^5$
- 1 <= `nums1[i]`, `nums2[j]` <= $10^9$
- Both `nums1` and `nums2` are sorted in non-decreasing orde
:::

---

# 解法

## 概念

今天使用 two pointers 的作法解決，簡單來說就是想辦法讓兩個指標是接近的，如果有一樣就回傳

另一個做法是 set，set 應該就是使用 binary search 讓時間降低吧！

## 程式碼

```python=
class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        n1 = len(nums1)
        n2 = len(nums2)
        ptr1 = 0
        ptr2 = 0
        while ptr1 < n1 and ptr2 < n2:
            if nums1[ptr1] == nums2[ptr2]:
                return nums1[ptr1]
            elif nums1[ptr1] < nums2[ptr2]:
                ptr1 += 1
            else:
                ptr2 += 1
        return -1
```

---

# 複雜度

## 時間複雜度

可能走訪完兩條 list，會是 $O(m+n)$

![TimeComplexity20240309](https://hackmd.io/_uploads/Hy9Z6RK6a.png =80%x)

## 空間複雜度

pointers 固定是兩支，所以是 $O(1)$

![SpaceComplexity20240309](https://hackmd.io/_uploads/H1nQpRtaa.png =80%x)