Minimum Common Value — Solution in Python, Java & C++
Minimum Common Value solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Minimum Common Value is an easy coding problem on arrays, hash table and binary search, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Binary Search, Two Pointers
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two integer arrays nums1 and nums2, both sorted in non-decreasing order, return the smallest integer that appears in both. If they share no value, return -1.
Example 1
Input: nums1 = [1,2,3], nums2 = [2,4]
Output: 2
Example 2
Input: nums1 = [1,2,3,6], nums2 = [2,3,4,5]
Output: 2
Example 3
Input: nums1 = [1,3], nums2 = [2,4]
Output: -1
Constraints
1 <= nums1.length, nums2.length <= 401 <= nums1[i], nums2[j] <= 100Both arrays are sorted in non-decreasing order.
Hints for Minimum Common Value
Hint 1
Both arrays are already sorted, so a merge-style two-pointer walk suffices.
Hint 2
Advance whichever pointer sits on the smaller value; equality is the answer.
Hint 3
Walking from the front means the first match found is automatically the smallest.
How to solve Minimum Common Value
Merge-walk the two sorted arrays: advance the pointer on the smaller value, and the first equality is the smallest common value.
Approach
- Set
i = j = 0. - If
nums1[i] == nums2[j], return it; else advance the pointer on the smaller value. - Return
-1when either array runs out.
Why it works
Both pointers only move forward past values that cannot be common, so the first match is the minimum common element.
Complexity
- Time —
O(n + m) - Space —
O(1)
Pitfalls
- A hash set of one array is O(n + m) time but O(n) space; the merge uses none.
Reference solution
Python
def getCommon(nums1, nums2) -> int:
i = 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 -1Java
public static int getCommon(int[] nums1, int[] nums2) {
int i = 0, j = 0;
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;
}C++
int getCommon(vector<int>& nums1, vector<int>& nums2) {
size_t i = 0, j = 0;
while (i < nums1.size() && j < nums2.size()) {
if (nums1[i] == nums2[j]) return nums1[i];
if (nums1[i] < nums2[j]) i++;
else j++;
}
return -1;
}JavaScript
var getCommon = function(nums1, nums2) {
let i = 0, j = 0;
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;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets