Today we are going to go over another problem which is to square a sorted array. This seems super simple, you just loop through and multiply each number by itself and then push it into a new result array and then return it. However there are edge cases that make this problem more difficult than it seems, like negative numbers, when they get squared, they become positive but when they’re squared into a positive number, they will throw off the sorted array. We need to find a way to return the array sorted without using the built in sort() function that exists in many languages. Lets go over how to approach this problem..
Here we have what we discussed earlier. The easy and simple solution you think of when you first see this problem. This will definitely pass some test cases, so if you got this far, you’re killing it. But when we insert a negative number like -4 and square it, it becomes a positive number, 16, and will probably be larger than some of the other squared positive numbers in the input array. So now that we have our result array all set up with all the numbers squared we need to go about sorting it without using the built in sort method because, well, where’s the fun in that.
To sort this array, we’re first going to need some variables to compare elements in the array and keep track of as we go. One variable for the smallest index in the array which would be at index 0 and one for the largest index which would be at the end of the array, array.length — 1. Once we have these two initialized we need to loop backwards through the resultArray we created earlier. We do this to ensure that whichever number is larger always ends up towards the end of the array. Next, we check the integers at the smallest index and the largest index and compare them, whichever is larger will end up at the end of our array. Here is what that looks like in code..
Now THAT is some good looking code, beautiful for sure and it will pass all of our test cases. Now you have a handy way of sorting an array for the future. While this is another question that seems simple it is crucial for your understanding of algorithms and data structures. Practice writing this one out a few times and get comfortable with hand sorting your own array. Until next time! Take care!