easyArray ProblemsJava

Find the Intersection of Two Sorted Arrays

Return the values that appear in both of two ascending-sorted arrays.

Quick Answer

Keep one pointer in each sorted array. If the two current elements are equal, record it and advance both pointers. Otherwise advance the pointer at the smaller element. This finds all common values in O(m + n) time without any extra lookup structure.

Problem Statement

Given two arrays that are each sorted in ascending order, return the values that appear in both. Because the arrays are sorted, you can find the common elements with a single coordinated pass rather than comparing every pair.

For example, the intersection of [1, 2, 4, 5, 6] and [2, 3, 5, 7] is [2, 5].

Input: Two ascending-sorted integer arrays a (length m) and b (length n).

Output: An array of the values present in both inputs, in ascending order.

Examples

Example 1
Input:  a = [1, 2, 4, 5, 6], b = [2, 3, 5, 7]
Output: [2, 5]

2 and 5 are the only values found in both arrays.

Example 2
Input:  a = [2, 4, 6, 8], b = [4, 8, 10]
Output: [4, 8]

4 and 8 are shared; 2, 6, and 10 appear in only one array.

Constraints

  • 0 <= m, n <= 10^6
  • Both inputs are sorted in non-decreasing order

Think Before You Code

Reveal the questions to ask yourself first
  • How does the arrays being sorted let you avoid comparing every element to every other?
  • When the two current elements differ, which pointer should move, and why?
  • What do you do when the two current elements are equal?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
Because both arrays are sorted, you can sweep them together with one pointer each.
Hint 2
If `a[i] < b[j]`, then `a[i]` can never match anything later in `b`, so advance `i`.
Hint 3
When `a[i] == b[j]`, that value is common — record it and advance both pointers.

Approach

Reveal the step-by-step approach

A synchronized two-pointer walk over the sorted arrays.

  1. Start i = 0, j = 0, and an empty result list.
  2. While i < m and j < n:
    • If a[i] < b[j], increment i (a[i] is too small to match).
    • Else if a[i] > b[j], increment j.
    • Else they are equal: add the value and increment both i and j.
  3. When either pointer runs off its array, no more matches are possible; stop.

Each step advances at least one pointer, so the loop runs at most m + n times.

Dry Run

Walk through the example step by step

Intersecting a = [1, 2, 4, 5, 6], b = [2, 3, 5, 7]:

i | j | a[i] | b[j] | comparison | action        | result
--+---+------+------+------------+---------------+-------
0 | 0 | 1    | 2    | a<b        | i++           | []
1 | 0 | 2    | 2    | a==b       | add 2, i++,j++| [2]
2 | 1 | 4    | 3    | a>b        | j++           | [2]
2 | 2 | 4    | 5    | a<b        | i++           | [2]
3 | 2 | 5    | 5    | a==b       | add 5, i++,j++| [2,5]
4 | 3 | 6    | 7    | a<b        | i++ (a ends)  | [2,5]

Solution

Reveal the full Java solution
import java.util.ArrayList;
import java.util.List;

public class IntersectionSortedArrays {
    public static List<Integer> intersection(int[] a, int[] b) {
        List<Integer> result = new ArrayList<>();
        int i = 0, j = 0;
        while (i < a.length && j < b.length) {
            if (a[i] < b[j]) {
                i++;
            } else if (a[i] > b[j]) {
                j++;
            } else {
                result.add(a[i]);
                i++;
                j++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(intersection(
            new int[]{1, 2, 4, 5, 6}, new int[]{2, 3, 5, 7})); // [2, 5]
        System.out.println(intersection(
            new int[]{2, 4, 6, 8}, new int[]{4, 8, 10})); // [4, 8]
    }
}

Sorting lets us reason locally: if a[i] is smaller than b[j], no later element of b can equal a[i] (they only grow), so we can safely discard a[i] by advancing i. Equality yields a match. Because at least one pointer advances every iteration, the total work is O(m + n) with no hash structure required.

Time: O(m + n)Space: O(1) beyond the output list

Common Mistakes

  • Advancing both pointers on an inequality, which can skip over a genuine match.
  • Assuming the arrays are unsorted and reaching for a HashSet, discarding the O(m+n) sorted advantage.

Edge Cases to Test

  • Disjoint arrays should return an empty result.
  • Either array empty should return an empty result.
  • Distinct sorted inputs yield a strictly increasing intersection.

Interview Follow-Ups

  • How would you handle duplicate matches when both arrays contain repeats?
  • How would you intersect two unsorted arrays, and what is the cost?
  • How would you extend this to the intersection of three sorted arrays?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us