Minimum Common Value

Easy
269.

Minimum Common Value

Minimum Common Value is an easy coding problem on arrays, hash table and binary search, asked in Amazon and Google interviews.

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 <= 40
  • 1 <= nums1[i], nums2[j] <= 100
  • Both arrays are sorted in non-decreasing order.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var getCommon = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 40
  • 1 <= nums1[i], nums2[j] <= 100
  • Both arrays are sorted in non-decreasing order.

Hints for Minimum Common Value

  1. Hint 1

    Both arrays are already sorted, so a merge-style two-pointer walk suffices.

  2. Hint 2

    Advance whichever pointer sits on the smaller value; equality is the answer.

  3. 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

  1. Set i = j = 0.
  2. If nums1[i] == nums2[j], return it; else advance the pointer on the smaller value.
  3. Return -1 when 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 -1

Java

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