Articles

Blogs

MCQ

SQL

Q&A

Tools

Tags

Jobs

News

Community

LogIn

Email

Password

Show Password

Forget Password

I don't have account.Sign Up!

Login

‹ ›

‹ ›

‹ ›

Sponsored -55%

Tarkan Top Brand

Tarkan Portable Folding Laptop Desk with Drawer, Cup & Tablet Holder (Black)

Foldable · Anti-slip strip · 60 × 40 cm · No assembly

★★★★★★★★★★ 4.2 (7,877) 1K+ bought last month

₹899 M.R.P. ₹1,999Save ₹1,100

Buy Now →

Adℹ

✕

Intersection of Two Sorted Arrays

HackFury

Last Updated : 05 October 2025

37 Views

#array

#sorting

#coding-problems

#two-pointers

Adℹ

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

Approach	Time Complexity	Space Complexity
Brute Force (Nested Loops)	O(n × m)	O(m)
Binary Search	O(n log m)	O(m)
Two Pointers (Optimal)	O(n + m)	O(1)

Trending Developer Reads

Rippling SDE-2 Interview Experience (4+ Years Experience) | Offer Received | Coding, LLD & System Design

Google L4 Software Engineer III interview experience | Selected

Amazon SDE-2 Interview Experience (3 Years Experience)

Meesho SDE-1 Backend Interview Experience (Remote | 3 Round) - Rejected

Meesho SDE-1 Online Assessment Interview Experience (Remote) - Rejected

Uber SDE-2 Interview Experience : LLD, HLD, DSA & Hiring Manager Round

System Design Deep Dive: 25 Essential Interview Questions

System Design Interview – BIGGEST Mistakes to Avoid

Top 50+ SQL Interview Questions and Answers for Intermediate to Advanced

Visa Software Engineer 1 (SDE-1) Interview Experience | CodeSignal OA + Graph-Based Technical Rounds

Responses (0)

Write a response

Hide Comments

No Comments yet.

‹ ›

‹ ›

‹ ›

‹ ›

Sponsored -53%

Zebronics #1 Best Seller

ZEBRONICS Blanc Slim Wireless Mouse — Rechargeable, BT + 2.4GHz (Black)

Up to 1600 DPI · Silent clicks · 63g · Multicolor LED

★★★★★★★★★★ 4.0 (9,512) 5K+ bought last month

₹376 M.R.P. ₹799Save ₹423

Buy Now →

‹ ›

‹ ›

‹ ›

‹ ›

Sponsored -34%

iQOO Amazon's Choice

iQOO Z10 Lite 5G — Cyber Green, 4GB RAM, 128GB Storage

Dimensity 6300 · 50MP Sony AI Camera · 6000 mAh · IP64

★★★★★★★★★★ 4.0 (2,052) 500+ bought last month

₹18,997 M.R.P. ₹28,999Save ₹10,002

Buy Now →

\n \n \n \n \n

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

\n
• \n

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

  \n
\n
• \n

  Result must also be in sorted order.

  \n
\n

Example 1

Input:\narr1 = [1, 2, 2, 3, 4]\narr2 = [2, 2, 4, 6]\n\nOutput: [2, 2, 4]\n

Example 2

Input:\narr1 = [1, 1, 2, 3, 5]\narr2 = [1, 1, 1, 2, 4, 5]\n\nOutput: [1, 1, 2, 5]\n

Constraints:

\n
• \n

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

  \n
\n
• \n

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

  \n
\n
• \n

  Both arrays are sorted in non-decreasing order

  \n
\n

Brute Force Approach (Nested Loops)

Compare every element of the first array (arr1) with every element of the second array (arr2).\nWhenever 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

\n
• \n

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

  \n
\n
• \n

  For each element arr1[i]:

  \n
  \n
  • \n

    Traverse all elements in arr2.

    \n
  \n
  • \n

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

    \n
    \n
    • \n

      Add it to the result list.

      \n
    \n
    • \n

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

      \n
    \n
    • \n

      Break (move to next element in arr1).

      \n
    \n
    \n
  \n
  \n
\n

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

Complexity Analysis

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

Better Approach — Using Binary Search

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

The key optimization lies in the sorted property:

\n
• \n

  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).

  \n
\n
• \n

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

  \n
\n

Step-by-Step Approach

\n
• \n

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

  \n
\n
• \n

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

  \n
\n
• \n

  For each element in the smaller array:

  \n
  \n
  • \n

    Perform a binary search in the larger array.

    \n
  \n
  • \n

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

    \n
  \n
  • \n

    Mark that index as visited.

    \n
  \n
  \n
\n
• \n

  Return the result list.

  \n
\n

\nimport java.util.*;\n\npublic class IntersectionSortedArrays {\n    public static List<Integer> intersectionBinarySearch(int[] arr1, int[] arr2) {\n        List<Integer> result = new ArrayList<>();\n        if (arr1.length > arr2.length) {\n            return intersectionBinarySearch(arr2, arr1);\n        }\n        boolean[] visited = new boolean[arr2.length];\n        for (int num : arr1) {\n            int index = Arrays.binarySearch(arr2, num);\n\n            if (index >= 0 && !visited[index]) {\n                result.add(num);\n                visited[index] = true;\n            }\n        }\n        return result;\n    }\n    public static void main(String[] args) {\n        int[] arr1 = {1, 2, 2, 3, 4};\n        int[] arr2 = {2, 2, 3, 5};\n        System.out.println(intersectionBinarySearch(arr1, arr2)); // [2, 2, 3]\n    }\n}\n

Complexity Analysis

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

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.\nThis method eliminates redundant searches entirely and achieves linear time complexity.

Core Idea

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

\n
• \n

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

  \n
\n
• \n

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

  \n
\n
• \n

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

  \n
\n

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

Step-by-Step Logic

\n
• \n

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

  \n
\n
• \n

  While both pointers are within array bounds:

  \n
  \n
  • \n

    Compare arr1[i] and arr2[j].

    \n
  \n
  • \n

    Move pointers as per conditions:

    \n
    \n
    • \n

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

      \n
    \n
    • \n

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

      \n
    \n
    • \n

      If equal : add to result, increment both.

      \n
    \n
    \n
  \n
  \n
\n
• \n

  Continue until one array is completely traversed.

  \n
\n
• \n

  Return the result list.

  \n
\n

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

Complexity Analysis

\n
• Time Complexity:\tO(n + m)\tEach array is traversed once
\n
• Space Complexity:\tO(1)\tOnly a few pointers used (excluding output)
\n

Complexity Comparison