arrays
intersection
algorithm
sorted
integers

How to intersect two sorted integer arrays without duplicates?

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

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.


Course illustration
Course illustration

All Rights Reserved.