We have to find the middle element when 3 sorted arrays are merged to form a single sorted array without using extra space so we cannot actually merge the array.
Search for kth element in n sorted arrays.
It’s a standard question.
1 Like
we can do it in linear time.
As we just want to find the middle element of the final sorted array.So we already Know the index of the required element.
(l1+l2+l3)/2 i.e all total number of element divided by 2.
we can do it just like we do to merge 2 sorted array
take 3 pointers each pointing to the initial element of the arrays
and one more pointer to track the element of final array.
and break the loop when we get the desired index.
3 Likes
1 Like
Thank you guys for replying.You guys are amazing.
why the 4th pointer?
it will point to the current size of the sorted array. here i am not creating another array it is just a variable that stores the current size of the sorted array if this variable is equal to the required index the our search for the middle element is over
It is actually a naive approach compared to time complexity. But slightly optimised compared to space complexity.
ohk… So we can break when the 4th pointer is equal to (total size of all array)/“2” ?
yup when it is equal to (total element)/2;
and return the last element.
1 Like