# Minimum Common Value
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-common-value)
Canonical: https://scaleengineer.com/dsa/problems/minimum-common-value
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table
---
## 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 <= 105`
* `1 <= nums1[i], nums2[j] <= 109`
* Both `nums1` and `nums2` are sorted in **non-decreasing** order.

# Approaches
## Brute Force with Nested Loops
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int getCommon(int[] nums1, int[] nums2) {
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                if (num1 == num2) {
                    return num1;
                }
            }
        }
        return -1;
    }
}
```
### Algorithm
- Iterate through `nums1` with an index `i` from 0 to `nums1.length - 1`.
- Inside this loop, iterate through `nums2` with an index `j` from 0 to `nums2.length - 1`.
- If `nums1[i]` is equal to `nums2[j]`, you have found the first common element. Since `nums1` is sorted, this must be the minimum common value. Return `nums1[i]`.
- If the loops complete without finding any common element, return -1.

## Binary Search
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Iterate through each element `num` in 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 `num` in `nums2`, it is a common element. Since we are iterating through the first array in sorted order, this must be the minimum common value. Return `num`.
- If the loop finishes without finding any common element, return -1.

## Hash Set
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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 `num` in 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.

## Two Pointers
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.
**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.
**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.
### Explanation
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 than `nums2[j]`, we know `nums1[i]` cannot be a common value with `nums2[j]` or any subsequent element in `nums2` (since `nums2` is sorted). So, we advance the pointer `i` to consider the next element in `nums1`.
- If `nums1[i]` is greater than `nums2[j]`, we similarly advance the pointer `j`.
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.

```java
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
    }
}
```
### Algorithm
- Initialize two pointers, `i = 0` for `nums1` and `j = 0` for `nums2`.
- Loop as long as both pointers are within the bounds of their respective arrays (`i < nums1.length` and `j < nums2.length`).
- Compare `nums1[i]` and `nums2[j]`:
  - If `nums1[i] == nums2[j]`, you've found the minimum common value. Return `nums1[i]`.
  - If `nums1[i] < nums2[j]`, increment `i` to find a potentially larger, matching value in `nums1`.
  - If `nums1[i] > nums2[j]`, increment `j` to find a potentially larger, matching value in `nums2`.
- If the loop terminates, it means one pointer has gone past the end of its array, so no common element was found. Return -1.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```