Intersection of Two Sorted Arrays

JavaView on GFG

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?