Welcome to my second post on code challenges! Last post was all about how to approach a challenge. We discussed the UPER Problem Solving Framework. For those that are new, UPER stands for Understand, Plan, Execute and Reflect.

Understand

So for today’s code challenge we will be going over Median of Two Sorted Arrays. The spec says that there are two sorted arrays, nums1 and nums2, of an undetermined size. They actually listed their sizes as “m and n respectively”. That means it could be empty or it could have a length of 2200 or anything in between or beyond. I imagine that you can’t have a negative length. The spec also mentions that “You may assume nums1 and nums2 cannot be both empty.” If this was an in person whiteboard interview I would ask for clarification on that. Do they mean they cannot both be empty at the same time? For example, nums1= [] and nums2 =[]. Or do they mean neither one can be empty? For example, nums1= [] and nums2 = [1,2,3,4,5].

Since this is an online coding challenge I am going to take it literally. For the examples they give us we have nums1 = [1,3] and nums2 = [2]. The median of these is 2.0 (Notice how I did a float and not a regular integer). For the second example we are given nums1= [1,2] and nums2=[3,4] They explained that the median is 2.5 because (2+3)/2=2.5. Hmmm. . . Why would they divide 2 and 3? Why is the median of the first example 2.0?

Okay so it seems that they are kind of mentally putting the integers in one sorted array and finding the median. Kinda like 4th grade math here. So let’s review since that was a long time ago for a lot of us.

Mean, Median and Mode

Mean is the average, median is the middle of a sorted list, and mode is the the integer that shows up the most. In this problem we only care about the median.

Example of finding median:
Our Sorted List => 5, 10, 20, 22, 27, 32, 42
I like to basically remove one from the front, one from the back and repeat until I get just one integer left. 
5, 10, 20, 22, 27, 32, 42 => 10, 20, 22, 27, 32, 42 => 10, 20, 22, 27, 32 => 20, 22, 27, 32 => 20, 22, 27 => 22, 27 => 22 

Median of our sorted list is 22.

But, what would happen if our list was an even length, thus leading to two “medians”? Again, let’s go back to the fourth grade. You have to find the Mean, or average of the two numbers.

Example of finding the median #2:
Our Sorted List => 10, 20, 22, 27, 32, 42 => 20, 22, 27, 32, 42 => 20, 22, 27, 32 => 22, 27, 32 => 22, 27
(22 + 27) / 2 = 24.5

So that is how we would find the median if we were normal people. But let’s face it, we are developers. We are not normal people. We have to write instructions in another language to a computer on how to do what we just did.

Plan

Before we even start real coding we are going to do something called Psuedocoding. For those that are new, Psuedo = Fake. Psuedocoding = Fake coding. It is the easiest way to just let your thoughts flow and get your ideas down without having to think about syntax or even what language you want to solve this in.

// We need to find the median
// Median is the middle of a sorted list
// How do we find the middle?
    // Let's first find our total length by adding the length of both arrays
    // Lets divide it by 2 or maybe use the modulus (%) operator   <====== It's okay to have multiple game plans. 
//In fact, I highly encourage it. If at first you don't succeed, try your second idea.
   // Definitely need to loop over the arrays somehow => for loop maybe?
        // We need to find the smallest number and remove it for every iteration
            // if the lengths of both arrays are the same
                //  and if the first item of the second array is greater than the first item in the first array
                    // remove and return the first item in the first array
                // else
                    // remove and return the first item of the second array
            // otherwise
                // if first array has a length that is not 0
                    // remove and return first item of first array
                // else
                    // remove and return first item of second array
  // If the total length is odd
       // Then return the last number we removed from the sorted arrays
  // Else
       // Take the last number we removed and add it to the new smallest number and divide by two

Whew! That is a lot. If you didn’t come up with this on your own, do not worry. These are called challenges for a reason.

Execute

Okay now the fun stuff! Let’s code. I did this one in JavaScript because it’s important not to get rusty, even if Python is superior.

// We need to find the median
var findMedianSortedArrays = function(nums1, nums2) {
// Let's first find our total length by adding the length of both arrays
    const length = nums1.length + nums2.length
// Instantiate a new variable on the global scope 
// so that I may use it in my for loop while having the ability to use it outside of the loop
    let last;
// Definitely need to loop over the arrays somehow => for loop maybe?
    for(let i = 0; i < length/2; i+=1){
// We need to find the smallest number and remove it for every iteration
        last = min(nums1, nums2)
    }
 // If the total length is odd
    if (length % 2 != 0){
// Then return the last number we removed from the sorted arrays
        return last
    }
     else{
 // Take the last number we removed and add it to the new smallest number and divide by two
        return (last + min(nums1, nums2))/2
    }
};

function min(n1, n2){
// if the lengths of both arrays are the same
  if (n1.length && n2.length){
// if the first item of the second array is greater than the first item in the first array
     if (n2[0] > n1[0]){
 // remove and return the first item in the first array
        return n1.shift()
    }
 // remove and return the first item of the second array
     else{
       return n2.shift()
    }
  }
    else{
  // if first array has a length that is not 0
      if (n1.length > 0){
// remove and return the first item in the first array
        return n1.shift()
     }
// remove and return the first item of the second array
      else{
         return n2.shift()
      }
  }
}
   

Reflect

Does this compile? Is our code optimal? Could I make more readable? What could I improve upon? After answering those questions you can decide how you want to move forward.

Didn’t compile? Let’s return to the spec and make sure we understand it correctly and work from there.

Runtime is too slow? Maybe we can do something else besides a for loop. Or maybe move away from arrays. (Note: I don’t think that is possible for this solution but if you figure it out please let me know!)

Could someone else pick this code up and know exactly what was going on? If not, then maybe look at how you are naming things. Maybe creating intuitive variable names would make it better.

Thank you for reading! I love feedback so please leave comments below.