Help with array sort please ... 😢

So I am solving this problem at leetcode :- Median of Two Sorted Arrays

everything was going fine until they gave me the input of -ve numbers in the array, it all went bad that second.

here’s my code :-

var findMedianSortedArrays = function(nums1, nums2) {
    var arr3 = [...nums1 , ...nums2];
    arr3.sort();
    function medi(arr) {
  if(arr.length % 2 == 0){
    return (arr[(arr.length/2) - 1] + arr[(arr.length/2)])/2;
  }
  else if(arr.length % 2 != 0 ) {
    return arr[Math.floor(arr.length/2)]
  }
}

return medi(arr3)
};

I was initially thinking of a way to flip the array if it has negative digits, but I soon realized what if in between those negative there was also a +ve digit?

So hoping someone could help me with this problem, the effort will be greatly appreciated :slightly_smiling_face: :+1:

are you sure this do what you want? check documentation on sort method
image

1 Like

Yeah, sort is by character point, so you end up with 1, 10, 1000, 2, 222, 3 if you don’t use the callback to tell JS how you want it sorted.

That aside, just glancing at this

var arr3 = [...nums1 , ...nums2];
arr3.sort();

is an issue immediately. You have two sorted arrays already. You don’t have to sort anything.

Technically, I think can just iterate
½•(nums1.length + nums2.length), don’t need any extra array or anything.

The description is normally really important for these toy brainteaser problems, you need to think carefully about exactly what you’re given for the problem

Also, running Math.floor on an integer gives that integer: the if/else logic after the sort is unnecessary

2 Likes

Just read about it on mozilla web docs, I get how it works now. Thank you for the reminder :laughing: :+1:

Well the given arrays are sorted themselves but don’t we need an array made of both of the given arrays to find the median?
If we do need that array we form it by adding the given two arrays up , and here is where I think we will need to sort because if there is are two arrays ex. [1,3] & [2] , we do need 2 to come before 3 don’t we ? else we will get 3 as the median…
Please do provide your thoughts on it . :slightly_smiling_face:

Here’s the solution I found out using mozilla web docs.
I learnt about callback functions, and how sort() can use it to properly sort the array.
Here’s my new solution :-

var findMedianSortedArrays = function(nums1, nums2) {
    var arr3 = [...nums1 , ...nums2];
    function compare(a,b)  {
        return a - b;
    }
    arr3.sort(compare);
    function medi(arr) {
  if(arr.length % 2 == 0){
    return (arr[(arr.length/2) - 1] + arr[(arr.length/2)])/2;
  }
  else if(arr.length % 2 != 0 ) {
    return arr[Math.floor(arr.length/2)]
  }
}

return medi(arr3)
};

Pretty simple now eh? :sweat_smile:

No, you know

  1. where the middle point is (you already know the length

and

  1. what order the values come in, they are already sorted

The issue with yours is:

  • you make copies of the two arrays
  • create another array
  • merge the two copied arrays
  • sort them again

You don’t need to do any of that, you just need to iterate the values until you hit the halfway point.

What you’ve written is fine most of the time IRL. But for leetcode (or similar) game, the aim is to be as efficient as possible, and yours is extremely inefficient, you’re redoing a load of work that’s already been done for you.

Yours is a solution to “you are given two unsorted arrays, find the median of both of them”

1 Like

Thank you, I will try my best to solve it the way you explained, I am a beginner by the way so thank you for furthering your explanation :+1:

:+1: I’m trying not to explain too much. With these puzzles/games you need think very carefully about the items you’re given: there is normally a specific solution. And very often (not all the time, but very often) that will use only very basic primitives. Try a few different approaches as well.

1 Like

you need to find the median of the whole array tho
if one array is [2,7,15,22] and the other is [1,2,3], how do you know what’s the median without merging them? (3)

or do something like check both arrays at the same time with two iterators, and increasing only one of them until you find the median (in this case it would be the 4th number)?

1 Like

Yep, latter.

Quickest way I can see is you can check if arr1[0] or arr2[0] is smaller, that’s first value, then say it’s arr1[0], then check is arr[1] or arr2[0] is smaller, that’s second value, and so on.

And as you already know how many times you need to do that to get the median, can just keep doing that until hit the middle point. I think needs at least four variables to track – one for arr1 index, one for arr2 index, one for which array last value came from, one for the median. I think: I need to write it down, the variables needed might be slightly different

Edit: also, it’s much easier conceptually to just push the values into an array (same as above but just push, means not as much tracking indices and values), but was trying to avoid creating any new objects when I was thinking about it

Edit: using splice to progressively delete values results in the simplest solution afaics, not as efficient as tracking the indices but it should be performant

Edit after writing some code:

one solution is to have two vars, one to store current and one to store previous values. Get n where n is total length/2. Two vars used to track current indices. Iterate. When the sum of those === n then stop iterating. Once stopped iterating either take current or (current + prev)/ 2 depending on whether n is odd or even.

1 Like

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.