Intersection of Two Sorted Arrays

JavaView on GFG

Problem Overview

Find common elements of two sorted arrays.

See our study guide for structured GFG and LeetCode practice.

Intuition

Find common elements of two sorted arrays. Two-pointer scan.

Algorithm

1i=0, j=0. While both in bounds: if equal: add to result, advance both. If arr1[i]<arr2[j]: i++. Else j++.

Common Pitfalls

• No duplicates in output (each element once). For duplicates: use same two-pointer but skip duplicates after match.

Intersection of Two Sorted Arrays.java

Java

// Approach: Use two pointers on the sorted arrays. Move the smaller pointer forward;
// when values match, append once (skip duplicates by checking last inserted value) and
// advance both pointers.
// Time: O(n + m) Space: O(1) extra (excluding output)

import java.util.*;

class Solution {

    ArrayList<Integer> intersection(int[] a, int[] b) {
        ArrayList<Integer> result = new ArrayList<>();

        int i = 0, j = 0;

        while (i < a.length && j < b.length) {
            if (a[i] == b[j]) {
                if (result.isEmpty() || result.get(result.size() - 1) != a[i]) {
                    result.add(a[i]);
                }
                i++;
                j++;
            } else if (a[i] < b[j]) {
                i++;
            } else {
                j++;
            }
        }

        return result;
    }
}

Was this solution helpful?