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.
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; }}Video 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.