Intersection of Two Sorted Arrays

Given two sorted arrays, return their intersection (the common elements).

• If an element appears more than once in both arrays, it should appear the same number of times in the intersection.

• Result must also be in sorted order.

Example 1

Input:
arr1 = [1, 2, 2, 3, 4]
arr2 = [2, 2, 4, 6]

Output: [2, 2, 4]

Example 2

Input:
arr1 = [1, 1, 2, 3, 5]
arr2 = [1, 1, 1, 2, 4, 5]

Output: [1, 1, 2, 5]

Constraints:

• 1 <= arr1.length, arr2.length <= 10^5

• -10^9 <= arr1[i], arr2[i] <= 10^9

• Both arrays are sorted in non-decreasing order

Brute Force Approach (Nested Loops)

Compare every element of the first array (arr1) with every element of the second array (arr2). Whenever a match is found add it to the result but to handle duplicates correctly, mark that element in arr2 as used so it isn’t counted again.

Steps

• Create a boolean array visited[] of size arr2.length to track which elements of arr2 are already matched.

• For each element arr1[i]:

  • Traverse all elements in arr2.

  • If arr1[i] == arr2[j] and visited[j] == false:

    • Add it to the result list.

    • Mark visited[j] = true to avoid duplicate counting.

    • Break (move to next element in arr1).

import java.util.*;

public class IntersectionSortedArrays {
    public static List<Integer> intersectionBruteForce(int[] arr1, int[] arr2) {
        List<Integer> result = new ArrayList<>();
        boolean[] visited = new boolean[arr2.length]; // track used elements
        for (int i = 0; i < arr1.length; i++) {
            for (int j = 0; j < arr2.length; j++) {
                if (!visited[j] && arr1[i] == arr2[j]) {
                    result.add(arr1[i]);
                    visited[j] = true;
                    break; // move to next arr1 element
                }
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 2, 3, 4};
        int[] arr2 = {2, 2, 3, 5};
        System.out.println(intersectionBruteForce(arr1, arr2)); // [2, 2, 3]
    }
}

Complexity Analysis

• Time Complexity: O(n × m), For each element in arr1, we scan arr2
• Space Complexity: O(m), For the visited[] array

Better Approach — Using Binary Search

When both arrays are sorted, we can do much better than nested loops. Instead of scanning linearly, we can use Binary Search to find matches efficiently.

The key optimization lies in the sorted property:

• For each element in one array, we can quickly check whether it exists in the other array using Binary Search in O(log n) time instead of O(n).

• We also ensure that duplicates are handled properly by marking visited elements.

Step-by-Step Approach

• Identify the smaller array. We'll iterate over it to reduce total operations. (If arr1 is larger, swap them.)

• Create a visited[] array for the larger one to track elements already matched.

• For each element in the smaller array:

  • Perform a binary search in the larger array.

  • If found and not visited, add it to the result list.

  • Mark that index as visited.

• Return the result list.

import java.util.*;

public class IntersectionSortedArrays {
    public static List<Integer> intersectionBinarySearch(int[] arr1, int[] arr2) {
        List<Integer> result = new ArrayList<>();
        if (arr1.length > arr2.length) {
            return intersectionBinarySearch(arr2, arr1);
        }
        boolean[] visited = new boolean[arr2.length];
        for (int num : arr1) {
            int index = Arrays.binarySearch(arr2, num);

            if (index >= 0 && !visited[index]) {
                result.add(num);
                visited[index] = true;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 2, 3, 4};
        int[] arr2 = {2, 2, 3, 5};
        System.out.println(intersectionBinarySearch(arr1, arr2)); // [2, 2, 3]
    }
}

Complexity Analysis

• Time Complexity: O(min(n, m) × log(max(n, m))), We perform a binary search for each element in the smaller array
• Space Complexity: O(max(n, m)), For the visited[] array
• Best Case: O(min(n, m)), When most elements are missing early
• Worst Case: O(n log m), For dense intersections

Optimal Approach — Two Pointer Technique

When both arrays are sorted, there’s an even better and more elegant way to find their intersection the Two Pointer Approach. This method eliminates redundant searches entirely and achieves linear time complexity.

Core Idea

We take advantage of the sorted property of both arrays. Using two pointers, one for each array, we move them intelligently based on their current values:

• If arr1[i] < arr2[j] : the smaller value cannot be part of the intersection, so move i forward.

• If arr1[i] > arr2[j] : move j forward.

• If arr1[i] == arr2[j] : we found a common element! Add it to the result and move both pointers forward.

This ensures we only traverse each array once no nested loops, no extra searches.

Step-by-Step Logic

• Initialize two pointers : i = 0 (for arr1), j = 0 (for arr2).

• While both pointers are within array bounds:

  • Compare arr1[i] and arr2[j].

  • Move pointers as per conditions:

    • If arr1[i] < arr2[j] : increment i.

    • If arr1[i] > arr2[j] : increment j.

    • If equal : add to result, increment both.

• Continue until one array is completely traversed.

• Return the result list.

import java.util.*;

public class IntersectionSortedArrays {
    public static List<Integer> intersectionTwoPointer(int[] arr1, int[] arr2) {
        List<Integer> result = new ArrayList<>();
        int i = 0, j = 0;
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] < arr2[j]) {
                i++;
            } else if (arr1[i] > arr2[j]) {
                j++;
            } else {
                result.add(arr1[i]);
                i++;
                j++;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 2, 3, 4, 5};
        int[] arr2 = {2, 2, 3, 5, 6};
        System.out.println(intersectionTwoPointer(arr1, arr2)); // [2, 2, 3, 5]
    }
}

Complexity Analysis

• Time Complexity: O(n + m) Each array is traversed once
• Space Complexity: O(1) Only a few pointers used (excluding output)

Complexity Comparison