Smallest Difference Coding Challenge

    For this weeks challenge I decided to do another more difficult problem called the smallest difference. The way this challenge works is you are given 2 lists each containing integers. Your job is to return the pair of integers one from each list that produces the absolute difference that is closest to 0. The items you will return will be in a new list containing the pair for example [3,2]. I found a way to create 2 different solutions for this problem and after researching online I am starting to learn optimal solutions for different problems. I have not gotten to the course in my degree that we learn optimal space and time complexity using big 0 notation so I do not know the exact verbiage yet however it is obvious that if you have a solution that requires to for loops instead of just one while loop the 2 for loops will take longer time than the while loop since you have to traverse your lists 2 times. 

    The first solution I did which was not the optimal solution is also called the naive solution. The first thing that came to mind when I heard the problem was to write two for loops, each traversing each list given and creating variable to hold the absolute difference of both elements and keeping track if that is lower than our current lowest difference. At every step we have to update our current lowest absolute difference we would just update our pairs in our return list to whatever those 2 integers were. We also initialize our smallest variable to equal infinity that way when we calculate the first difference we will always at least have one smallest difference. This of course is an easy way to solve this problem but as I was reading online if this was a job interview your interviewer might ask you if this is the most optimal solution for this problem. This is where I came up with the second solution.

    The way our second solution works is we have to sort both arrays that way they are in order from minimum to maximum. Before I explain the code this is an outline of how it will work. We will start at index 0 of both elements and we will take the absolute difference of both pairs. Lets say we have num1 and num2 from respective lists. We first see which of those 2 numbers is greater or equal then. Since we also sorted both lists we know that every number after that initial element will be greater than the element at index 0. Lets say num1 is greater than num2. We calculate the absolute difference and save it. Then we have to increment the index of the list that num2 belongs to because if we were to update the index of list 1 then we would be getting farther away from 0. That is because if num1 =10 and num2 = 3 if we were to then go to the second index in list one that number would either be greater than or equal to 10. That would take us away from the smallest difference. In contrast by updating the index of list two we know that num2 will either be 3 or greater than 3. That would get us to our goal. It would be the opposite if if num2 was greater than num1. Now if num1 and num2 equal each other then we would return that pair to the user because that would be the smallest difference. If both nums equal the same amount there cant be any other combination of numbers that would produce a smaller difference than 0 so we terminate the program. 

    Now to the actual code of this optimal solution. We first sort both lists that are given by the user. We then initialize two variables that will keep track of index1 for list 1 and index2 of list 2. These will be initialized to 0 since since we want to begin by comparing the first 2 values in both of our lists. We then create a variable called smallest that will keep track of the smallest difference and current which will keep track of the current difference. We will have those 2 initialized to infinity that way any first value we calculate will always be smaller than infinity. We also initialize an empty list which we will use to return the smaller pair to the user. We will then use a while loop to traverse through both of our arrays at the same time. We will do this till the index we are at for both indexes is less than the length of both lists. That is because if we allowed it to continue we would get an out of bounds error. We then initialized 2 variables inside of our while loop that will keep track of the elements we are at in both lists. We then check if num1 is less than num2. Inside of that condition if it is we then sub num2 from num1 and update our current. After that we increment the index of list 1. If num2 was less than num1 we would do the exact opposite and increment our index at list 2. Our third case is if both num1 and num2 equal each other which in that case we would terminate the program and just return a list to the user with num1 and num2. If one of our first 2 cases hit instead of case 2 we check if current is less than smallest. If it is we update our smallest to equal current and update our pairs inside of our return list. We will do this till we get to the last element in either list. If we break out of our while loop we will return the return list to our user. As you can see we used one traversal that goes through both lists at the same time which is optimal. In our first solution we used 2 for loops and in the optimal solution we simply used 1 while loop.