Minimum Common Value solution and explanation
Google
9 more videos on this problem
2540. Minimum Common Value | 3 Approaches | HashMap | 2 Pointers | Binary SearchAryan Mittal · 9:48 · 2K views
Leetcode | 2540. Minimum Common Value | Easy | Java SolutionDeveloper Docs · 5:34 · 1K views
2540 minimum common value | leetcode daily challenge | DSA | Shashwat Tiwari HindiShashCode · 14:05 · 1K views
Minimum Common Value || Biweekly Contest 96 LeetCode Solution with ExplanationLearn to Code · 3:39 · 1K views
2540. Minimum Common Value (Leetcode Easy)Programming Live with Larry · 3:43 · 716 views
2540. Minimum Common Value | Leetcode Daily - PythonLeetcode Daily · 5:51 · 251 views
2540. Minimum Common Value | Leetcode | Approach and code | Pythoncodingwithme · 2:49 · 250 views
LeetCode 2540 : Minimum Common Value || EASY || JAVA || Detailed SolutionCodeGPT · 13:10 · 222 views
Daily LeetCode Challenge: 2540.Minimum Common Value | C++ | 2-Approaches | Hashmap | 2-PointersSHWETA BHAGAT · 11:49 · 114 views
Leetcode 2540 || Minimum Common Value || Leetcode Daily Easy || cppKomal Pal · 6:01 · 78 views
The problem
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.
Approach overview
Problem Overview: You are given two sorted integer arrays. The goal is to return the smallest value that appears in both arrays. If no such value exists, return -1. Since both arrays are already sorted in non‑decreasing order, you can exploit that property instead of checking every possible pair.
Approach 1: Two-Pointer Technique (O(n + m) time, O(1) space)
This approach leverages the sorted nature of both arrays. Start two pointers: i for nums1 and j for nums2. Compare the elements at both pointers. If the values are equal, that value is the smallest common element because both arrays are sorted and pointers move from the beginning. If nums1[i] < nums2[j], increment i to move toward a larger value. Otherwise increment j. Each step eliminates one element from consideration, so the arrays are scanned only once.
The key insight is that increasing the pointer on the smaller value moves closer to a potential match without missing any candidate. This makes the algorithm linear in the combined size of the arrays. It uses constant extra memory and is the most efficient solution when both arrays are sorted. This pattern appears frequently in two pointers and array problems where ordered data allows simultaneous traversal.
Approach 2: HashSet Intersection (O(n + m) time, O(n) space)
This method ignores the sorted property and instead relies on fast membership checks using a hash table. Insert all elements of the first array into a HashSet. Then iterate through the second array and check whether each value exists in the set. The first matching value encountered that also satisfies the "minimum" requirement can be tracked and returned.
Hash lookups run in average O(1) time, making the overall complexity linear relative to the total number of elements. The tradeoff is memory usage: storing the first array requires O(n) extra space. This technique demonstrates the classic tradeoff between time and space and is a common pattern in hash table problems where quick existence checks are required.
Binary Search Variation (O(n log m) time, O(1) space)
Because the arrays are sorted, you could also iterate through one array and perform a binary search for each value in the other. For every element in nums1, run binary search in nums2. If found, return the value immediately. This approach highlights how binary search works on sorted collections, though it is slower than the two‑pointer scan when both arrays must be processed.
Recommended for interviews: The two-pointer technique is the expected solution. It uses the sorted property directly and achieves optimal O(n + m) time with constant space. Mentioning the hash set approach shows you understand alternative strategies, but recognizing that sorted arrays allow a linear merge-style scan demonstrates stronger algorithmic thinking.
Approach 1: Two-Pointer Technique
This approach utilizes the fact that both arrays are sorted. Using two pointers, one for each array, we traverse the arrays to find the smallest common value:
- Initialize two pointers at the start of each array.
- Compare the elements pointed by the pointers.
- If both elements are equal, you've found the minimum common integer.
- If the element at the first pointer is less than the element at the second pointer, increment the first pointer; otherwise, increment the second pointer.
- Continue this process until a match is found or one of the pointers reaches the end of its respective array.
- If no common element is found, return -1.
def find_min_common_value(nums1, nums2):
i, j = 0, 0
while i < len(nums1) and j < len(nums2):
if nums1[i] == nums2[j]:
return nums1[i]
elif nums1[i] < nums2[j]:
i += 1
else:
j += 1
return -1
nums1 = [1, 2, 3]
nums2 = [2, 4]
result = find_min_common_value(nums1, nums2)
print(result)public class Main {
public static int findMinCommonValue(int[] nums1, int[] nums2) {
int i = 0, j = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] == nums2[j]) {
return nums1[i];
} else if (nums1[i] < nums2[j]) {
i++;
} else {
j++;
}
}
return -1;
}
public static void main(String[] args) {
int[] nums1 = {1, 2, 3};
int[] nums2 = {2, 4};
System.out.println(findMinCommonValue(nums1, nums2));
}
}#include <iostream>
#include <vector>
int findMinCommonValue(const std::vector<int>& nums1, const std::vector<int>& nums2) {
int i = 0, j = 0;
while (i < nums1.size() && j < nums2.size()) {
if (nums1[i] == nums2[j]) {
return nums1[i];
} else if (nums1[i] < nums2[j]) {
++i;
} else {
++j;
}
}
return -1;
}
int main() {
std::vector<int> nums1 = {1, 2, 3};
std::vector<int> nums2 = {2, 4};
std::cout << findMinCommonValue(nums1, nums2) << std::endl;
return 0;
}function findMinCommonValue(nums1, nums2) {
let i = 0, j = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] === nums2[j]) {
return nums1[i];
} else if (nums1[i] < nums2[j]) {
i++;
} else {
j++;
}
}
return -1;
}
const nums1 = [1, 2, 3];
const nums2 = [2, 4];
console.log(findMinCommonValue(nums1, nums2));#include <stdio.h>
int findMinCommonValue(int *nums1, int nums1Size, int *nums2, int nums2Size) {
int i = 0, j = 0;
while (i < nums1Size && j < nums2Size) {
if (nums1[i] == nums2[j]) {
return nums1[i];
} else if (nums1[i] < nums2[j]) {
i++;
} else {
j++;
}
}
return -1;
}
int main() {
int nums1[] = {1, 2, 3};
int nums2[] = {2, 4};
int result = findMinCommonValue(nums1, 3, nums2, 2);
printf("%d\n", result);
return 0;
}using System;
public class Program
{
public static int FindMinCommonValue(int[] nums1, int[] nums2)
{
int i = 0, j = 0;
while (i < nums1.Length && j < nums2.Length)
{
if (nums1[i] == nums2[j])
{
return nums1[i];
}
else if (nums1[i] < nums2[j])
{
i++;
}
else
{
j++;
}
}
return -1;
}
public static void Main()
{
int[] nums1 = {1, 2, 3};
int[] nums2 = {2, 4};
Console.WriteLine(FindMinCommonValue(nums1, nums2));
}
}Using Python's list indexing and a simple while-loop structure similar to other languages, this solution finds the minimum common element using the two-pointer technique efficiently.
Time Complexity: O(n + m)
Space Complexity: O(1)
Approach 2: HashSet Intersection
This approach uses a HashSet to store the elements of the smaller array, providing a quick way to check for common elements:
- Insert all elements of the smaller array into a HashSet to minimize space usage.
- Iterate through the larger array and for each element, check if it exists in the HashSet.
- If a common element is found, return it as the minimum common value due to sorted order.
- If not, return -1 after iterating through the array.
- This ensures we keep the lookup time for elements O(1) by using HashSet.
def find_min_common_value(nums1, nums2):
set_nums1 = set(nums1)
for num in nums2:
if num in set_nums1:
return num
return -1
nums1 = [1, 2, 3]
nums2 = [2, 4]
result = find_min_common_value(nums1, nums2)
print(result)import java.util.HashSet;
public class Main {
public static int findMinCommonValue(int[] nums1, int[] nums2) {
HashSet<Integer> set = new HashSet<>();
for (int num : nums1) {
set.add(num);
}
for (int num : nums2) {
if (set.contains(num)) {
return num;
}
}
return -1;
}
public static void main(String[] args) {
int[] nums1 = {1, 2, 3};
int[] nums2 = {2, 4};
System.out.println(findMinCommonValue(nums1, nums2));
}
}#include <iostream>
#include <vector>
#include <unordered_set>
int findMinCommonValue(const std::vector<int>& nums1, const std::vector<int>& nums2) {
std::unordered_set<int> set(nums1.begin(), nums1.end());
for (int num : nums2) {
if (set.find(num) != set.end()) {
return num;
}
}
return -1;
}
int main() {
std::vector<int> nums1 = {1, 2, 3};
std::vector<int> nums2 = {2, 4};
std::cout << findMinCommonValue(nums1, nums2) << std::endl;
return 0;
}function findMinCommonValue(nums1, nums2) {
let smallerSet = new Set(nums1);
for (let num of nums2) {
if (smallerSet.has(num)) {
return num;
}
}
return -1;
}
const nums1 = [1, 2, 3];
const nums2 = [2, 4];
console.log(findMinCommonValue(nums1, nums2));#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int findMinCommonValue(int *nums1, int nums1Size, int *nums2, int nums2Size) {
if (nums1Size > nums2Size) {
// Swap to always iterate the smaller array
int *temp = nums1;
nums1 = nums2;
nums2 = temp;
int tmpSize = nums1Size;
nums1Size = nums2Size;
nums2Size = tmpSize;
}
qsort(nums1, nums1Size, sizeof(int), compare);
for (int i = 0; i < nums2Size; i++) {
if (bsearch(&nums2[i], nums1, nums1Size, sizeof(int), compare)) {
return nums2[i];
}
}
return -1;
}
int main() {
int nums1[] = {1, 2, 3};
int nums2[] = {2, 4};
printf("%d\n", findMinCommonValue(nums1, 3, nums2, 2));
return 0;
}using System;
using System.Collections.Generic;
public class Program
{
public static int FindMinCommonValue(int[] nums1, int[] nums2)
{
HashSet<int> set = new HashSet<int>(nums1);
foreach (int num in nums2)
{
if (set.Contains(num))
return num;
}
return -1;
}
public static void Main()
{
int[] nums1 = {1, 2, 3};
int[] nums2 = {2, 4};
Console.WriteLine(FindMinCommonValue(nums1, nums2));
}
}This Python solution uses Python's set data structure to conveniently test for the presence of elements in constant time. We insert elements of one array into a set and test elements of the other array against it.
Time Complexity: O(n + m)
Space Complexity: O(min(n, m)), which holds elements of the smaller array in a set.
Approach 3: 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).
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;
}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
}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
}
}Approach 4: Default Approach
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
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Technique | Time Complexity: O(n + m) |
| HashSet Intersection | Time Complexity: O(n + m) |
| Two Pointers | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(n + m) | O(1) | Best choice when both arrays are sorted and you want the optimal linear scan |
| HashSet Intersection | O(n + m) | O(n) | Useful when arrays are not guaranteed to be sorted or quick lookups are preferred |
| Binary Search | O(n log m) | O(1) | Works well when one array is much smaller than the other |
Frequently asked questions
Is Minimum Common Value easy or hard?
Minimum Common Value is categorized as an Easy problem. The core idea is recognizing that both arrays are sorted and applying a two-pointer traversal. Once that pattern is identified, the implementation is straightforward.
Minimum Common Value Python/Java solution
Most implementations follow the same logic across languages. In Python or Java, use two indices to traverse the arrays while comparing values. If elements match, return the value; otherwise move the pointer with the smaller element.
How to solve Minimum Common Value in O(n)?
Traverse both sorted arrays simultaneously using two pointers. Compare the current elements and advance the pointer pointing to the smaller value. When both values are equal, return that value as the minimum common element. This produces O(n + m) time complexity with constant space.
What is the best approach for Minimum Common Value?
The two-pointer technique is the best approach because both arrays are already sorted. Start pointers at the beginning of each array and move the pointer pointing to the smaller value until both values match. This method runs in O(n + m) time and uses O(1) extra space, which is optimal.
Is Minimum Common Value asked at Google/Amazon/Meta?
Problems involving two-pointer scanning and set intersection frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of this problem test your ability to exploit sorted arrays and choose the correct data structure for membership checks.
What data structure is used in Minimum Common Value?
The optimal solution mainly uses pointer indices on arrays. An alternative solution uses a HashSet to store elements from one array and check membership while iterating through the other. The choice depends on whether you prioritize memory efficiency or implementation simplicity.
What is the time complexity of Minimum Common Value?
The optimal solution using the two-pointer technique runs in O(n + m) time, where n and m are the lengths of the two arrays. Each pointer moves forward at most once through its array. The space complexity is O(1).