Explorer
Data Structures & Algorithms

Find the union of two sorted arrays. The union must contain distinct elements in sorted order.

Problem Statement

Given two sorted arrays arr1 and arr2, return their union as a new sorted array containing only distinct elements.

Examples

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

Output: [1, 2, 3, 4, 5]

Explanation: Common elements are taken once.

Constraints

Standard constraints

Complexity

Time Complexity: O(N + M)

Space Complexity: O(N + M)

Hints

šŸ’” Hint 1: Both arrays are already sorted. Two pointers can merge them linearly without re-sorting. šŸ’” Hint 2: Compare arr1[i] and arr2[j]. Append the smaller element to result if it is not already equal to the last added element. šŸ’” Hint 3: After one array is exhausted, append remaining elements from the other while skipping consecutive duplicates.

Editorial & Approach

Problem Overview & Intuition

Because both arrays are already sorted, we can use a two-pointer merge approach similar to merge sort. By checking that an element does not equal the last element pushed into the result, we eliminate all duplicates on the fly in O(N + M) time.

Step-by-Step Approach

  1. Initialize two pointers i = 0 and j = 0 and an empty array result.
  2. While i < arr1.length && j < arr2.length: compare arr1[i] and arr2[j].
  3. Add the smaller value to result if result[result.length - 1] !== val.
  4. Advance pointer(s) accordingly.
  5. Drain remaining elements from arr1 and arr2.
  6. Return result.

Optimal Implementation (JavaScript)

function findUnion(arr1, arr2) {
  const result = [];
  let i = 0, j = 0;
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      if (!result.length || result[result.length - 1] !== arr1[i]) result.push(arr1[i]);
      if (arr1[i] === arr2[j]) j++;
      i++;
    } else {
      if (!result.length || result[result.length - 1] !== arr2[j]) result.push(arr2[j]);
      j++;
    }
  }
  while (i < arr1.length) {
    if (!result.length || result[result.length - 1] !== arr1[i]) result.push(arr1[i]);
    i++;
  }
  while (j < arr2.length) {
    if (!result.length || result[result.length - 1] !== arr2[j]) result.push(arr2[j]);
    j++;
  }
  return result;
}

Complexity Analysis

Time Complexity O(N + M) ā€” each element in both arrays inspected once.
Space Complexity O(N + M) ā€” for the output union array.

Edge Cases & Corner Traps Handled

  • Arrays with completely disjoint values: all elements included.
  • Identical arrays: returns one instance of each distinct element.
  • Arrays containing internal duplicates: duplicates collapsed properly.

Union of Two Sorted Arrays

Easy
Given two sorted arrays arr1 and arr2, return their union as a new sorted array containing only distinct elements.
Example Scenarios
1Example 1
Input: arr1 = [1, 2, 3, 4, 5], arr2 = [2, 3, 4, 4, 5]
Output: [1, 2, 3, 4, 5]
Explanation:

Common elements are taken once.

Constraints
ā€¢Standard constraints
Editor
Loading Editor...
arr1 =
[1, 2, 3, 4, 5]
arr2 =
[2, 3, 4, 4, 5]
Output:Click "Run" above to execute and verify your code here.
[1,2,3,4,5]