Description#
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:
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:
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:
1 <= nums1.length, nums2.length <= 1051 <= nums1[i], nums2[j] <= 109- Both
nums1 and nums2 are sorted in non-decreasing order.
Solutions#
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.
The time complexity is $O(m + n)$, where $m$ and $n$ are the lengths of the two arrays respectively. The space complexity is $O(1)$.
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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int getCommon(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
for (int i = 0, j = 0; i < m && j < n;) {
if (nums1[i] == nums2[j]) {
return nums1[i];
}
if (nums1[i] < nums2[j]) {
++i;
} else {
++j;
}
}
return -1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int getCommon(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
for (int i = 0, j = 0; i < m && j < n;) {
if (nums1[i] == nums2[j]) {
return nums1[i];
}
if (nums1[i] < nums2[j]) {
++i;
} else {
++j;
}
}
return -1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func getCommon(nums1 []int, nums2 []int) int {
m, n := len(nums1), len(nums2)
for i, j := 0, 0; i < m && j < n; {
if nums1[i] == nums2[j] {
return nums1[i]
}
if nums1[i] < nums2[j] {
i++
} else {
j++
}
}
return -1
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| function getCommon(nums1: number[], nums2: number[]): number {
const m = nums1.length;
const n = nums2.length;
let i = 0;
let j = 0;
while (i < m && j < n) {
if (nums1[i] === nums2[j]) {
return nums1[i];
}
if (nums1[i] < nums2[j]) {
i++;
} else {
j++;
}
}
return -1;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| impl Solution {
pub fn get_common(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let m = nums1.len();
let n = nums2.len();
let mut i = 0;
let mut j = 0;
while i < m && j < n {
if nums1[i] == nums2[j] {
return nums1[i];
}
if nums1[i] < nums2[j] {
i += 1;
} else {
j += 1;
}
}
-1
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int getCommon(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int i = 0;
int j = 0;
while (i < nums1Size && j < nums2Size) {
if (nums1[i] == nums2[j]) {
return nums1[i];
}
if (nums1[i] < nums2[j]) {
i++;
} else {
j++;
}
}
return -1;
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| impl Solution {
pub fn get_common(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let mut iter1 = nums1.iter();
let mut iter2 = nums2.iter();
let mut num1 = iter1.next();
let mut num2 = iter2.next();
while let (Some(n1), Some(n2)) = (num1, num2) {
if n1 == n2 {
return *n1;
} else if n1 < n2 {
num1 = iter1.next();
} else {
num2 = iter2.next();
}
}
-1
}
}
|
