Union of 2 Sorted with Duplicates | Explained with Images

Given two sorted arrays a[] and b[], where each array may contain duplicate elements , the task is to return the elements in the union of the two arrays in sorted order.

Here’s the [Problem Link] to begin with.

OPTIMAL SOLUTION

1. Problem Statement

The goal is to produce the union of two sorted arrays a and b, such that the resulting array result is also sorted and contains no duplicates. This task requires merging and deduplicating the elements of both arrays effectively.

Input:

• a: A sorted list of integers.
• b: Another sorted list of integers.

Output:

• A list of integers representing the union of a and b, sorted and without duplicates.

2. Intuition and Approach

This approach uses the two-pointer technique to efficiently merge two sorted arrays while ensuring no duplicates. The pointers i and j traverse arrays a and b respectively:

1. Compare the current elements of both arrays.
2. Append the smaller or equal element to the result if it’s not the same as the last appended element.
3. Increment the pointer in the array from which the element was taken.
4. Continue this process until one or both of the arrays are fully traversed.
5. After exiting the main loop, if any elements are left in either array, they are added to the result, ensuring duplicates are not added.

3. Code

def sortedArray(a: [int], b: [int]) -> [int]:
    i = 0
    j = 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            if len(result) == 0 or result[-1] != a[i]:
                result.append(a[i])
            i += 1
        else:
            if len(result) == 0 or result[-1] != b[j]:
                result.append(b[j])
            j += 1

    while i < len(a):
        if len(result) == 0 or result[-1] != a[i]:
            result.append(a[i])
        i += 1

    while j < len(b):
        if len(result) == 0 or result[-1] != b[j]:
            result.append(b[j])
        j += 1

    return result

1. Two-Pointer Technique:
   1. The i and j pointers are initialized at the start of arrays a and b.
   2. A while loop continues as long as there are elements to process in both arrays.
2. Comparison and Addition:
   1. Inside the loop, compare a[i] to b[j].
   2. Append the smaller or equal value to result if it is not the same as the last element in result (to avoid duplicates).
   3. Increment the respective pointer (i or j).
3. Processing Remaining Elements:
   1. Once the main while loop exits (when one of the arrays is exhausted), the remaining elements in either a or b (or both) are added to result. The additional while loops ensure no duplicates are added.
4. Finalizing the Union:
   1. The process ensures all elements from both arrays are considered, and the union is sorted and duplicate-free due to the initial sorting and the checks during insertion.

4. Dry Run

Let’s go through the code step by step, using images to illustrate the detailed dry run process.

5. Edge Cases

• Empty Arrays: If either a or b is empty, the code correctly handles and appends the contents of the non-empty array to result.
• Identical Arrays: If a and b are the same, the method effectively adds each element once.
• Arrays with No Common Elements: If a and b share no common elements, all elements from both arrays are included in the union.

6. Time and Space Complexity

• Time Complexity: O(n+m), where n is the length of array a and m is the length of array b. Each element in both arrays is processed at most once.
• Space Complexity: O(n+m) for the result array in the worst case, where no elements are duplicated between a and b.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.