Leetcode diary: Merge Sorted Array

https://leetcode.com/problems/merge-sorted-array

problem is: given two sorted arrays, how do you produce a sorted array. One array have m count of numbers and the other has n count. The first array has m+n length so you don't need to worry about changing the array length.

This problem is easy if you just put the result in another array and mutate the m+n array in the end. So we'll opt in the hardest route O(m+n) with in place mutation only.

The first thing you have to accept is that the m and n values matter. It's a bit deceptive because the easy route doesn't really require it so people might overlook that and go down a terrible route.

The second is that you have to use the count as is, don't try to do m-- for some clever trick, just have a usual index loop through and you'll be just fine.

However you have to account for the fact that you can't just use for loops. This is because you have two arrays and aim for O(m+n), regular for loops can't do that.

So it's a while loop with conditions.

What are the conditions? It's easy to start out with something like:
while (indexM < m || indexN <n)
but that wouldn't really work because the final length is m+n, so it's more than that probably.

Then my thinking was:
Q: when the loop end?
A: it ends when all the numbers are in-place mutated
Q: how many numbers are there?
A: m+n
Q: but how do I represent that in code?
A: count until m+n?
Q: that doesn't feel right ...

If you ever get this feeling, it means something is missing for you to come up with the feels-right answer. You must step back and look at the other pieces of the problem.

I looked back at the in-place part of the question. In-place mutation of an array should immediately trigger you to need a third array to hold the values for; an extension of having a third variable for swapping two values in an array.
let's say it's: const holdM = [];

With that in mind, it should be apparent that the loop will end when:
indexN === n || hold.length ==0, which translates to:
while(indexN < n || holdM.length) {

now we can finally move on to writing the core code!

Given the problem we have two parts to the code:
1.) find current min value
2.) mutate array with current min

the first one is simple, we have 3 values:
1.) current value of array[m]
2.) of array2[n]
3.) holderM value

However we have to take care of each case because
1.) array[m] can be undefined since array length = m+n and only have value in the first m length
2.) array2 only have n values, you have to represent "array2 is exhausted" in code.
3.) holderM may or may not have values, also may have more than one values in the array.

to take care of that we can translate the code into:
const valM = indexM < m ? nums1[indexM] : Number.MAX_SAFE_INTEGER;
const valN = indexN < n ? nums2[indexN] : Number.MAX_SAFE_INTEGER;
valHold = holdM.length ? holdM[0] : Number.MAX_SAFE_INTEGER;

why only holdM[0]? it's because the smallest value is in the beginning of the array (you can also opt-in for last, doesn't matter).

so we finally have:
minVal = Math.min(valHold, valM, valN);

now we need to do something with the min value.
We have 3 cases to cover:
1.) minVal = current val of M
2.) minVal = current val of N
3.) minVal = current val of holdM

if it's
1.) we don't need to do anything, the current value is already in the array in its right place!
2.) it means values of N needs to be in place of M, therefore you'd need to push the M value to the holdM.
Then mutate the array to put in N value
3.) you need to push M value to hold M as do number 2 and mutate holdM value in.

The last thing to take care in this big explanation is that you have to have indexM and indexN. You will only increment indexN when N is the smallest value (case 2) and you'll always increment indexM, because you are always mutating on M.

full code below:

var merge = function(nums1, m, nums2, n) {
    const oriM = m;
    const oriN = n;
    let indexM=0, indexN=0, valM, valN, valHold, minVal;
    const holdM = [];
    while(indexN < n || holdM.length) {
        valHold = holdM.length ? holdM[0] : Number.MAX_SAFE_INTEGER;
        valM = indexM < m ? nums1[indexM] : Number.MAX_SAFE_INTEGER;
        valN = indexN < n ? nums2[indexN] : Number.MAX_SAFE_INTEGER;
        minVal = Math.min(valHold, valM, valN);

        if(minVal === valM) {
            indexM++; 
            continue; 
        }
        if (minVal === valN) {
            if (indexM < m) holdM.push(valM);
            nums1[indexM] = valN;
            indexN++;
        } 
        else if(minVal === valHold) {
            if (indexM < m) { holdM.push(valM); }
            nums1[indexM] = holdM.shift();
        }


        indexM++; 
    }
};

One last thing to note, the interviewer might be picky and ask what's the big O of this algorithm. It's not TRULY O(m + n) because of shift(). Shift() mutates the whole holdM at once. You should be fine if you acknowledge that caveat and say this could be easily remedied if we have a third variable indexHoldM and use that instead... Then god forbids that they talk about the length of the array. You'll need to then explain that you can just initiate the array with length m+n. Hopefully not...and hopefully that interviewer won't be on your team lol ...

Please hit me with a follow if you’d like to see more content, I’ll update irregular but somewhat frequently.

If you’d like a 1-1 conversation with me going over your resume or your career trajectory in general, please reach out to me at https://www.fiverr.com/kevtseng

Socials:
www.twitter.com/KevinTseng1991
https://www.linkedin.com/in/kevintseng1991/