arrays
intersection
algorithm
sorted
integers

How to intersect two sorted integer arrays without duplicates?

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

In this article, we will explore an efficient algorithm to intersect two sorted integer arrays without duplicates. A common problem in programming, it's crucial in scenarios where you need to determine the common elements in distinct datasets while maintaining computational efficiency. Given that the arrays are already sorted, our approach will take advantage of this property to achieve optimal performance.

Problem Definition

Given two sorted arrays A and B, our goal is to find their intersection, where each element in the result should appear as many times as it shows in both arrays. Since arrays are sorted and without duplicates, this problem can be solved efficiently.

Algorithm Explanation

We will utilize a two-pointer technique, essentially having one pointer for each array, to effectively traverse through the arrays and find common elements. This approach capitalizes on the sorted nature of the arrays and achieves optimal time complexity.

Steps:

  1. Initialize Pointers: Start by initializing two pointers, i and j, to traverse arrays A and B, respectively.
  2. Traverse Arrays: Use a loop to iterate through both arrays simultaneously:
    • If A[i] is less than B[j], increment i.
    • If A[i] is greater than B[j], increment j.
    • If A[i] equals B[j], it means we have found a common element. Add A[i] (or B[j]) to the result and increment both i and j.
  3. End of Array Check: The loop continues until we reach the end of one of the arrays.

Code Example

python
1def intersect_sorted_arrays(A, B):
2    i, j = 0, 0
3    intersection = []
4    
5    while i < len(A) and j < len(B):
6        if A[i] < B[j]:
7            i += 1
8        elif A[i] > B[j]:
9            j += 1
10        else:
11            intersection.append(A[i])
12            i += 1
13            j += 1
14            
15    return intersection
16
17# Example usage
18A = [1, 2, 4, 5, 7]
19B = [2, 5, 6, 7, 8]
20print(intersect_sorted_arrays(A, B))  # Output: [2, 5, 7]

Complexity Analysis

  • Time Complexity: The algorithm operates in O(n+m)O(n + m) time, where n is the length of array A and m is the length of array B. This is due to each element in both arrays being traversed at most once.
  • Space Complexity: The solution takes O(min(n,m))O(min(n, m)) space for the output array holding the common elements.

Considerations and Edge Cases

  • Empty Arrays: If either input array is empty, the result will also be an empty array as there are no common elements.
  • Different Array Lengths: The algorithm naturally handles arrays of different lengths, iterating only until the end of the shorter array.
  • No Common Elements: If there are no intersecting elements, the result will be an empty array.

Summary Table

Scenario / ConsiderationAction Taken / Result
Both arrays are emptyReturns an empty list
One array is emptyReturns an empty list
No common elementsReturns an empty list
Arrays with common itemsReturns a list of common items
ComplexityTime: O(n+m)O(n + m); Space: O(min(n,m))O(min(n, m))
Usage of two pointersEfficient traversal leveraging sorted properties of the arrays

Using the two-pointer technique, we achieve a linear traversal of both arrays, making our approach efficient and well-suited for scenarios requiring the intersection of sorted integer arrays without duplicates. This method is not only simple to implement but also provides optimal performance across a range of input sizes.


Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

All Rights Reserved.