Minimum Common Value
EasyPrompt
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
nums1andnums2are sorted in non-decreasing order.
Approaches
4 approaches with complexity analysis and trade-offs.
This approach involves iterating through every element of the first array and, for each element, comparing it with every element in the second array. Since the arrays are sorted, the first common element found is the minimum.
Algorithm
- Iterate through
nums1with an indexifrom 0 tonums1.length - 1. - Inside this loop, iterate through
nums2with an indexjfrom 0 tonums2.length - 1. - If
nums1[i]is equal tonums2[j], you have found the first common element. Sincenums1is sorted, this must be the minimum common value. Returnnums1[i]. - If the loops complete without finding any common element, return -1.
Walkthrough
The most straightforward solution is to use nested loops. The outer loop iterates through each element in nums1, and for each of these elements, the inner loop iterates through all elements in nums2 to find a match. When a match nums1[i] == nums2[j] is found, that number is a common value. Because nums1 is sorted in non-decreasing order, the first element from nums1 that is found to be common will be the smallest possible common value. Therefore, we can return this value immediately. If the loops complete without finding any matches, it means there are no common elements, and we return -1.
class Solution { public int getCommon(int[] nums1, int[] nums2) { for (int num1 : nums1) { for (int num2 : nums2) { if (num1 == num2) { return num1; } } } return -1; }}Complexity
Time
O(N * M), where N and M are the lengths of `nums1` and `nums2` respectively. In the worst-case scenario, we have to compare every element of `nums1` with every element of `nums2`.
Space
O(1), as no extra space proportional to the input size is used.
Trade-offs
Pros
Simple to understand and implement.
Cons
Highly inefficient with a quadratic time complexity, which will likely cause a 'Time Limit Exceeded' error on large inputs.
It does not take advantage of the fact that both arrays are sorted.
This approach improves upon the brute-force method by leveraging the fact that the arrays are sorted. We can iterate through one array and use binary search to efficiently check for the existence of each element in the other array.
Algorithm
- Iterate through each element
numin the shorter array (e.g.,nums1). - For each
num, perform a binary search for it in the longer array (e.g.,nums2). - If the binary search finds
numinnums2, it is a common element. Since we are iterating through the first array in sorted order, this must be the minimum common value. Returnnum. - If the loop finishes without finding any common element, return -1.
Walkthrough
Since the input arrays are sorted, we can optimize the search process. Instead of a linear scan through the second array for each element of the first, we can use binary search. The overall algorithm is to iterate through the elements of one array (say nums1) and for each element, use binary search to check if it exists in nums2. Because nums1 is sorted, the first element we find that also exists in nums2 will be the minimum common value. For a slight performance gain, it's better to iterate through the shorter array and perform the binary search on the longer one.
class Solution { public int getCommon(int[] nums1, int[] nums2) { // To optimize, iterate through the shorter array and search in the longer one. if (nums1.length > nums2.length) { return getCommon(nums2, nums1); } for (int num : nums1) { if (binarySearch(nums2, num)) { return num; } } return -1; } private boolean binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return true; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return false; }}Complexity
Time
O(N * log(M)), where N is the length of the array we iterate through and M is the length of the array we perform binary search on. This is a major improvement over the O(N*M) brute-force approach.
Space
O(1), as binary search can be implemented iteratively without using extra space.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Utilizes the sorted property of the arrays effectively.
Maintains a low space complexity.
Cons
While better than brute force, it's not the most optimal solution as a linear time approach exists.
This approach uses a hash set to store elements from one array, which allows for checking the existence of an element in constant average time. We then iterate through the second array to find the first common element.
Algorithm
- Create a
HashSet. - To optimize space, iterate through the shorter of the two arrays and add all its elements to the hash set.
- Iterate through the longer array.
- For each element
numin the longer array, check if it is present in the hash set. - Since the longer array is also sorted, the first element found in the set is the minimum common value. Return
num. - If the loop completes without finding a match, return -1.
Walkthrough
We can achieve a linear time solution by using a hash set. The idea is to trade space for time. First, we populate a hash set with all the elements from one of the arrays. To be memory-efficient, we should choose the smaller of the two arrays for this. Then, we iterate through the second array. For each element in the second array, we check if it exists in our hash set. Since the second array is sorted, the first element we find that is also in the hash set is guaranteed to be the minimum common value. If we finish iterating through the second array without finding a common element, we return -1.
import java.util.HashSet;import java.util.Set; class Solution { public int getCommon(int[] nums1, int[] nums2) { // Optimize space by creating the set from the smaller array. if (nums1.length > nums2.length) { return getCommon(nums2, nums1); } Set<Integer> set = new HashSet<>(); for (int num : nums1) { set.add(num); } for (int num : nums2) { if (set.contains(num)) { return num; } } return -1; }}Complexity
Time
O(N + M). It takes O(N) time to build the hash set from the first array and O(M) time to iterate through the second array.
Space
O(min(N, M)), where N and M are the lengths of the arrays. The space is used to store the elements of the smaller array in the hash set.
Trade-offs
Pros
Achieves linear time complexity, O(N + M), which is very efficient.
Conceptually simple: store and check.
Cons
Requires extra space to store the elements of one array, which can be significant if the array is large.
This is the most optimal approach, which fully utilizes the sorted property of both arrays. By using two pointers, one for each array, we can find the minimum common value in a single pass with constant extra space.
Algorithm
- Initialize two pointers,
i = 0fornums1andj = 0fornums2. - Loop as long as both pointers are within the bounds of their respective arrays (
i < nums1.lengthandj < nums2.length). - Compare
nums1[i]andnums2[j]:- If
nums1[i] == nums2[j], you've found the minimum common value. Returnnums1[i]. - If
nums1[i] < nums2[j], incrementito find a potentially larger, matching value innums1. - If
nums1[i] > nums2[j], incrementjto find a potentially larger, matching value innums2.
- If
- If the loop terminates, it means one pointer has gone past the end of its array, so no common element was found. Return -1.
Walkthrough
The most efficient way to solve this problem is by using the two-pointer technique. We initialize a pointer i to the start of nums1 and a pointer j to the start of nums2. We then iterate while both pointers are within their array bounds. In each step, we compare nums1[i] and nums2[j].
- If they are equal, we have found a common element. Since both pointers started at the beginning and only moved forward, this must be the minimum common element. We return it.
- If
nums1[i]is less thannums2[j], we knownums1[i]cannot be a common value withnums2[j]or any subsequent element innums2(sincenums2is sorted). So, we advance the pointerito consider the next element innums1. - If
nums1[i]is greater thannums2[j], we similarly advance the pointerj. This process continues until one of the pointers moves past the end of its array, at which point we know no common elements exist, and we return -1.
class Solution { public int getCommon(int[] nums1, int[] nums2) { int i = 0; // Pointer for nums1 int j = 0; // Pointer for nums2 while (i < nums1.length && j < nums2.length) { if (nums1[i] == nums2[j]) { return nums1[i]; } else if (nums1[i] < nums2[j]) { i++; } else { // nums1[i] > nums2[j] j++; } } return -1; // No common element found }}Complexity
Time
O(N + M), where N and M are the lengths of the arrays. In each step of the loop, at least one pointer is advanced. The total number of advancements is at most N + M.
Space
O(1), as it only requires a few variables to store the pointers, regardless of the input size.
Trade-offs
Pros
Optimal time complexity of O(N + M).
Optimal space complexity of O(1).
Makes a single pass through the arrays.
Cons
While optimal, the logic might be slightly less intuitive for beginners compared to the hash set approach.
Solutions
Solution
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; }}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; }};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 - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.