Union of two sorted arrays

Intuition

The union of two arrays will be all the unique elements of both of the arrays combined. So, using a set data structure will help & can find the distinct elements because the set does not hold any duplicates. As it is mandatory to preserve the order of the elements, use an ordered set.

Approach:

Declare a set s to store all the unique elements and a vector or list union to store the final answer.
Iterate through nums1 and nums 2 to store the elements in the set.
Now, iterate in the set and copy all the elements of the set to the answer vector and return it.

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> unionArray(vector<int>& nums1, vector<int>& nums2) {
       // Using unordered for storing unique elements
        set<int> s; 
        vector<int> Union;

        // Insert all elements of nums1 into the set
        for (int num : nums1) {
            s.insert(num);
        }

        // Insert all elements of nums2 into the set
        for (int num : nums2) {
            s.insert(num);
        }

        // Convert the set to vector to get the union
        for (int num : s) {
            Union.push_back(num);
        }

        return Union;
    }
};

int main() {
    // Initialize the arrays
    vector<int> nums1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    vector<int> nums2 = {2, 3, 4, 4, 5, 11, 12};
    
    // Create an instance of the Solution class
    Solution finder;
    
    /* Get the union of nums1 and 
    nums2 using the class method*/
    vector<int> Union = finder.unionArray(nums1, nums2);
    
    // Output the result
    cout << "Union of nums1 and nums2 is:" << endl;
    for (int val : Union) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}
import java.util.*;

class Solution {
    public int[] unionArray(int[] nums1, int[] nums2) {
        Set<Integer> set = new TreeSet<>();

        // Insert all elements of nums1 into the set
        for (int num : nums1) {
            set.add(num);
        }

        // Insert all elements of nums2 into the set
        for (int num : nums2) {
            set.add(num);
        }

        // Convert the set to an integer array to get the union
        int[] union = new int[set.size()];
        int index = 0;
        for (int num : set) {
            union[index++] = num;
        }

        return union;
    }

    public static void main(String[] args) {
        // Initialize the arrays
        int[] nums1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int[] nums2 = {2, 3, 4, 4, 5, 11, 12};

        // Create an instance of the Solution class
        Solution finder = new Solution();

        /* Get the union of nums1 and 
        nums2 using the class method */
        int[] union = finder.unionArray(nums1, nums2);

        System.out.println("Union of nums1 and nums2 is:");
        for (int val : union) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
}
from typing import List

class Solution:
    def unionArray(self, nums1, nums2):
        # Using set for storing unique elements
        s = set()
        Union = []

        # Insert all elements of nums1 into the set
        for num in nums1:
            s.add(num)

        # Insert all elements of nums2 into the set
        for num in nums2:
            s.add(num)

        # Convert the set to list to get the union
        for num in sorted(s):  # Sorting for union of sorted arrays
            Union.append(num)

        return Union
        
if __name__ == "__main__":
    # Initialize the arrays (lists in Python)
    nums1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    nums2 = [2, 3, 4, 4, 5, 11, 12]

    # Create an instance of the Solution class
    finder = Solution()

    """ Get the union of nums1 and 
    nums2 using the class method"""
    union = finder.unionArray(nums1, nums2)

    print("Union of nums1 and nums2 is:")
    print(" ".join(map(str, union)))
class Solution {
    unionArray(nums1, nums2) {
        // Using Set for storing unique elements
        let set = new Set();
        let union = [];

        // Insert all elements of nums1 into the set
        for (let num of nums1) {
            set.add(num);
        }

        // Insert all elements of nums2 into the set
        for (let num of nums2) {
            set.add(num);
        }

        /* Convert the set to an array and sort
        it to get the union in ascending order */
        union = Array.from(set).sort((a, b) => a - b);

        return union;
    }
}

// Main function to test the Solution class
const nums1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const nums2 = [2, 3, 4, 4, 5, 11, 12];

// Create an instance of the Solution class
const finder = new Solution();

/* Get the union of nums1 and
nums2 using the class method*/
const union = finder.unionArray(nums1, nums2);

console.log("Union of nums1 and nums2 is:");
console.log(union.join(" "));

Complexity Analysis

Time Complexity: O( (M+N)log(M+N) ), at max set can store M+N elements {when there are no common elements and elements in nums1 , nums2 are distntict}. So Inserting M+N th element takes log(M+N) time. Upon approximation across inserting all elements in worst, it would take O((M+N)log(M+N) time. Space Complexity: O(M+N), considering space of Union Array.

Intuition

The optimal approach uses the two-pointers to solve the problem. Use two pointers, one for each array, and traverse both arrays simultaneously. Keep adding the smaller element between the two arrays to the result vector if it hasn't been added already.

What if both elements are equal?

If both elements are equal, add any one of them, ensuring that all unique elements are added in sorted order.

Approach

Initialize two variable i to iterate nums1 and j to iterate nums2 as 0.

Create an empty vector for storing the union of nums1 and nums2.

If current element of nums1 is equal to current element of nums2, this means its a common element, so insert only one element in the union & increment it by 1.

If current element of nums1 is less than current element of nums2, insert current element of nums1 in union. Also check if last element in union vector is not equal to nums1[ i ],then insert in union else don’t insert. After checking increment i.

If current element of nums1 is greater than current element of nums2, insert current element of nums2 in union. Similar to last point, check if the last element in the union vector is not equal to nums2[ j ], then insert in the union, else don’t insert. After checking increment j.

This process will be taking place as:

After traversing if any elements are left in nums1 or nums2 check for condition and insert in the union.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> unionArray(vector<int>& nums1, vector<int>& nums2) {
        vector<int> Union; // Vector to store the union elements
        int i = 0, j = 0;
        int n = nums1.size();
        int m = nums2.size();

        while (i < n && j < m) {
              // Case 1 and 2
              if (nums1[i] <= nums2[j]){ 
    
                  if (Union.size() == 0 || Union.back() != nums1[i])
                      Union.push_back(nums1[i]);
                      i++;
                  } 
                 //case 3
                  else{
                      if (Union.size() == 0 || Union.back() != nums2[j])
                      Union.push_back(nums2[j]);
                      j++;
                  }
               }

       // If any element left in arr1
        while (i < n){ 
            if (Union.back() != nums1[i])
                Union.push_back(nums1[i]);
            i++;
        }
        // If any elements left in arr2
        while (j < m){ 
            if (Union.back() != nums2[j])
                Union.push_back(nums2[j]);
            j++;
        }

        return Union;
    }
};

int main() {
    vector<int> nums1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    vector<int> nums2 = {2, 3, 4, 4, 5, 11, 12};

    // Create an instance of the Solution class
    Solution finder;

    // Get union of nums1 and nums2 using class method
    vector<int> Union = finder.unionArray(nums1, nums2);

    cout << "Union of nums1 and nums2 is:" << endl;
    for (int val : Union) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}
import java.util.*;

class Solution {
    public int[] unionArray(int[] nums1, int[] nums2) {
        List<Integer> UnionList = new ArrayList<>();
        int i = 0, j = 0;
        int n = nums1.length;
        int m = nums2.length;

        while (i < n && j < m) {
             // Case 1 and 2
            if (nums1[i] <= nums2[j]) {
                if (UnionList.isEmpty() || UnionList.get(UnionList.size() - 1) != nums1[i]) {
                    UnionList.add(nums1[i]);
                }
                i++;
            } 
            // Case 3
            else {
                if (UnionList.isEmpty() || UnionList.get(UnionList.size() - 1) != nums2[j]) {
                    UnionList.add(nums2[j]);
                }
                j++;
            }
        }

        // Add remaining elements of nums1, if any
        while (i < n) {
            if (UnionList.isEmpty() || UnionList.get(UnionList.size() - 1) != nums1[i]) {
                UnionList.add(nums1[i]);
            }
            i++;
        }

        // Add remaining elements of nums2, if any
        while (j < m) {
            if (UnionList.isEmpty() || UnionList.get(UnionList.size() - 1) != nums2[j]) {
                UnionList.add(nums2[j]);
            }
            j++;
        }

        // Convert List<Integer> to int[]
        int[] Union = new int[UnionList.size()];
        for (int k = 0; k < UnionList.size(); k++) {
            Union[k] = UnionList.get(k);
        }

        return Union;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int[] nums2 = {2, 3, 4, 4, 5, 11, 12};

        // Create an instance of the Solution class
        Solution finder = new Solution();

        // Get union of nums1 and nums2 using class method
        int[] Union = finder.unionArray(nums1, nums2);

        // Output the result
        System.out.println("Union of nums1 and nums2 is:");
        for (int val : Union) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
}
from typing import List

class Solution:
    def unionArray(self, nums1: List[int], nums2: List[int]) -> List[int]:
        union = []#union set

        i, j = 0, 0
        n, m = len(nums1), len(nums2)

        while i < n and j < m:
           #case 1 and 2
            if nums1[i] <= nums2[j]:
                if not union or union[-1] != nums1[i]:
                    union.append(nums1[i])
                i += 1
           #case 3
            else:
                if not union or union[-1] != nums2[j]:
                    union.append(nums2[j])
                j += 1
        
        #if any elements left in nums1
        while i < n:
            if not union or union[-1] != nums1[i]:
                union.append(nums1[i])
            i += 1
        
        #if any elements left in nums2
        while j < m:
            if not union or union[-1] != nums2[j]:
                union.append(nums2[j])
            j += 1
        
        return union

    def main(self):
        nums1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
        nums2 = [2, 3, 4, 4, 5, 11, 12]

        # Create an instance of the Solution class
        finder = Solution()

        # Get union of nums1 and nums2 using class method
        union = finder.unionArray(nums1, nums2)

        print("Union of nums1 and nums2 is:")
        print(union)

if __name__ == "__main__":
    Solution().main()
class Solution {
    unionArray(nums1, nums2) {
        // Array to store the union elements
        let union = [];
        let i = 0, j = 0;
        let n = nums1.length;
        let m = nums2.length;

        while (i < n && j < m) {
            // Case 1 and 2
            if (nums1[i] <= nums2[j]) { 
                if (union.length === 0 || union[union.length - 1] !== nums1[i]) {
                    union.push(nums1[i]);
                }
                i++;
           // Case 3
            } else { 
                if (union.length === 0 || union[union.length - 1] !== nums2[j]) {
                    union.push(nums2[j]);
                }
                j++;
            }
        }

        // Add remaining elements of nums1, if any
        while (i < n) {
            if (union.length === 0 || union[union.length - 1] !== nums1[i]) {
                union.push(nums1[i]);
            }
            i++;
        }

        // Add remaining elements of nums2, if any
        while (j < m) {
            if (union.length === 0 || union[union.length - 1] !== nums2[j]) {
                union.push(nums2[j]);
            }
            j++;
        }

        return union;
    }

    main() {
        const nums1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
        const nums2 = [2, 3, 4, 4, 5, 11, 12];

        // Create an instance of the Solution class
        const finder = new Solution();

        // Get union of nums1 and nums2 using class method
        const union = finder.unionArray(nums1, nums2);

        console.log("Union of nums1 and nums2 is:");
        console.log(union);
    }
}

// Execute the main method if this script is run directly
if (require.main === module) {
    new Solution().main();
}

Complexity Analysis

Time Complexity: O(M+N), because both the arrays must be traversed once. Space Complexity: O(M+N)
The auxiliary space used is O(1) as no extra space is used. However, considering the space for returning the output, the overall space complexity will be O(M+N).

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach:

Solution:

Complexity Analysis

Intuition

What if both elements are equal?

Approach

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code