Problem

Given two sorted arrays nums1 and nums2, find the first intersection point (the smallest common element) between them. If there is no common element, return -1.

Examples

Example 1

1
2
3
4
5

Input:
  nums1 = [1, 2, 3, 6, 8, 10]
  nums2 = [4, 5, 6, 11, 15, 20]
Output: 6
Explanation: 6 is the first element present in both arrays.

Example 2

1
2
3
4
5

Input:
  nums1 = [1, 2, 3]
  nums2 = [4, 5, 6]
Output: -1
Explanation: There is no common element.
Similar Problems

Solution

Method 1 – Brute Force (Nested Loops)

Intuition

Compare every element of the first array with every element of the second array. Return the first match found.

Approach

  1. For each element in nums1, check all elements in nums2.
  2. If a match is found, return that element.
  3. If no match is found, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
  int intersectionPoint(vector<int>& nums1, vector<int>& nums2) {
    for (int x : nums1) {
      for (int y : nums2) {
        if (x == y) return x;
      }
    }
    return -1;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func intersectionPoint(nums1, nums2 []int) int {
  for _, x := range nums1 {
    for _, y := range nums2 {
      if x == y {
        return x
      }
    }
  }
  return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
  public int intersectionPoint(int[] nums1, int[] nums2) {
    for (int x : nums1) {
      for (int y : nums2) {
        if (x == y) return x;
      }
    }
    return -1;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
  fun intersectionPoint(nums1: IntArray, nums2: IntArray): Int {
    for (x in nums1) {
      for (y in nums2) {
        if (x == y) return x
      }
    }
    return -1
  }
}
1
2
3
4
5
6
7

class Solution:
  def intersection_point(self, nums1: list[int], nums2: list[int]) -> int:
    for x in nums1:
      for y in nums2:
        if x == y:
          return x
    return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
  pub fn intersection_point(nums1: &[i32], nums2: &[i32]) -> i32 {
    for &x in nums1 {
      for &y in nums2 {
        if x == y {
          return x;
        }
      }
    }
    -1
  }
}

Complexity

  • ⏰ Time complexity: O(n * m), where n and m are the lengths of the two arrays. Every pair is compared.
  • 🧺 Space complexity: O(1), no extra space used.

Method 2 – Two Pointers (Efficient)

Intuition

Since both arrays are sorted, we can use two pointers to efficiently find the first common element.

Approach

  1. Initialize two pointers, i and j, at the start of nums1 and nums2.
  2. While both pointers are within bounds:
  • If nums1[i] == nums2[j], return nums1[i].
  • If nums1[i] < nums2[j], increment i.
  • If nums1[i] > nums2[j], increment j.
  1. If no intersection is found, return -1.

Code

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

class Solution {
public:
  int intersectionPoint(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];
      else if (nums1[i] < nums2[j]) ++i;
      else ++j;
    }
    return -1;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func intersectionPoint(nums1, nums2 []int) int {
  i, j := 0, 0
  for i < len(nums1) && j < len(nums2) {
    if nums1[i] == nums2[j] {
      return nums1[i]
    } else 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 intersectionPoint(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;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  fun intersectionPoint(nums1: IntArray, nums2: IntArray): Int {
    var i = 0
    var j = 0
    while (i < nums1.size && j < nums2.size) {
      when {
        nums1[i] == nums2[j] -> return nums1[i]
        nums1[i] < nums2[j] -> i++
        else -> j++
      }
    }
    return -1
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
  def intersection_point(self, 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]
      elif 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

impl Solution {
  pub fn intersection_point(nums1: &[i32], nums2: &[i32]) -> i32 {
    let (mut i, mut j) = (0, 0);
    while i < nums1.len() && j < nums2.len() {
      if nums1[i] == nums2[j] {
        return nums1[i];
      } else if nums1[i] < nums2[j] {
        i += 1;
      } else {
        j += 1;
      }
    }
    -1
  }
}

Complexity

  • ⏰ Time complexity: O(n + m), where n and m are the lengths of the two arrays. Each element is checked at most once.
  • 🧺 Space complexity: O(1), only pointers are used.