As the final array contains element in stable-order, at any time we have 3 options for choosing the elements from A & B. 1- A[i] & A[i+1] 2- A[i] & B[I] 3- B[i] & B[i+1] we will choose that pair whose product is maximum. For ex:- A-2,1,3 B-3,7,9 C- 3,7,2,9,1,3 Its a linear time solution with constant time complexity. Algo :- 1 - Keep two indexes i=0 and j=0 pointing to arrays A & B respectively and k=0 for array C. 2 - Now , check the maximum of (a[i]*a[i+1], a[i]*b[j], b[j]*b[j+1] ). 3 - If a[i]*a[i+1] is maximum, add a[i],a[i+1] to C, i+=2. 4 - If a[i]*b[j] is maximum, add a[i],b[j] to C, i++,j++. 5 - If b[j]*b[j+1] is maximum, add b[j],b[j+1] to C, j+=2. 6 - k+=2. 7 - If i,j reached end, then break else Goto step 2. Time Complexity :- O(n) Space Complexity :- O(1)
-- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/6-JIwC7l-hYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
