Problem

Given two integer arrays nums1 and nums2, sorted in non-decreasing order, return theminimum 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.

Examples

Example 1

1
2
3

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

1
2
3

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 <= 10^5
  • 1 <= nums1[i], nums2[j] <= 10^9
  • Both nums1 and nums2 are sorted in non-decreasing order.

Solution

Method 1 – Two Pointers

Intuition

Since both arrays are sorted, we can efficiently find the minimum common value by scanning both arrays with two pointers. This avoids unnecessary comparisons and leverages the sorted property.

Approach

  1. Initialize two pointers, one for each array.
  2. While both pointers are within bounds:
    • If the values at both pointers are equal, return that value (it’s the smallest common).
    • If the value in nums1 is less, move its pointer forward.
    • If the value in nums2 is less, move its pointer forward.
  3. If no common value is found, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int getCommon(vector<int>& nums1, vector<int>& nums2) {
        int 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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func getCommon(nums1, nums2 []int) int {
    i, j := 0, 0
    for i < len(nums1) && j < len(nums2) {
        if nums1[i] == nums2[j] {
            return nums1[i]
        }
        if nums1[i] < nums2[j] {
            i++
        } else {
            j++
        }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public 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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun getCommon(nums1: IntArray, nums2: IntArray): Int {
        var i = 0
        var 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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def get_common(nums1: list[int], nums2: list[int]) -> int:
    i, j = 0, 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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn get_common(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let (mut i, mut j) = (0, 0);
        while i < nums1.len() && j < nums2.len() {
            if nums1[i] == nums2[j] {
                return nums1[i];
            }
            if nums1[i] < nums2[j] {
                i += 1;
            } else {
                j += 1;
            }
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    getCommon(nums1: number[], nums2: number[]): number {
        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;
    }
}

Complexity

  • ⏰ Time complexity: O(n + m), where n and m are the lengths of the arrays, as each element is visited at most once.
  • 🧺 Space complexity: O(1), only pointers and a few variables are used.