union

Problem Find Union and Intersection of two sorted arrays Example For example, if the input arrays are: arr1[] = {1, 3, 4, 5, 7} arr2[] = {2, 3, 5, 6} Then your program should print Union as {1, 2, 3, 4, 5, 6, 7} and Intersection as {3, 5}. Solution Algorithm Union(arr1[], arr2[]): For union of two arrays, follow the following merge procedure. Use two index variables i and j, initial values i = 0, j = 0 If arr1[i] is smaller than arr2[j] then print arr1[i] and increment i. [Read More]

Problem Given a sorted array of n elements followed by an unsorted array of length n. Sort the 2 list into one efficiently. Solution Method 1 - Insert the elements in sorted array using binary search Since inserting a single element into array and keeping it sorted is O(n), you cannot get better then that. Thus, for both cases - sorting the smaller array and then using merge(part1,part2) will be O(n), and thus optimal in terms of asymptotic complexity. [Read More]