You don't need to merge or sort the arrays. But it all depends on your goal. Assume the lengths of the lists are
M. As you are leet code, the "correct" answer is likely the complex solution, but in the real world, the simple and balanced solution is what I would reach for 90% of the time.
If you want a "reasonable" solution and move on with your life, merge then sort then take the middle is clear, maintainable, and fast "enough" at
If you care a bit more about performance, you can walk along the two arrays simultaneously, advancing in whichever has the smaller number. When you have consumed half the numbers you are at the median. This is more complex, but doesn't require allocations and is
O(N+M) compute time.
If you really care about performance and are prepared to write complex code. You can actually be even faster and get down to
O(log(N+M)). This will involve playing with the definition of median, thinking what it looks like to have identified the median elements, and then doing something akin to a binary search. Hint,
i+j == (N+M)/2, roughly, depending on parity of
This is more complex, it's harder to maintain, and much more time to work out. But if you need to do this repeatedly, the better asymptotic behaviour (the
O() function) might be worth it.