Coding: How to Square A Sorted Array In Python
The skills we demoed here can be learned through taking Data Science with Machine Learning bootcamp with NYC Data Science Academy.
LinkedIn | GitHub | Email | Data | Web App
Given a sorted list of integers, square the elements and give the output in sorted order.
Let's take a look at a very straightforward solution first:
def SortedSquares (arr):
# We will use list comprehension to square our list
temp = [x**2 for x in arr]
# Now that we have our list squared we can use the sorted function to return our answer
return sorted(temp)While this solution is correct, it takes up additional space because the sorted function makes a copy of our original list. This could be mitigated by using the sort function, but beware, make sure that the original list will not be needed as the sort() function mutates the list. Additionally, this solution is relatively slow. We need to go through every element in the list when we square the list and then we take 0 (log n) time to sort (Python does do a good job in the internal sorting algorithms for us). Can we modify the solution to make it faster? Yes!
def SortedSquares (arr):
# since we know the list is sorted we can simply look at the first and last elements magnitude to know which square will be larger
# let's start with two pointers, one at element [0] and one at element [arr_length - 1]
left, right = 0, len(arr)-1
# we'll need to keep track of how many elements we've sorted so we'll initialize a tracker. We also initialize an result list to store our answer
tracker = len(arr) - 1
final = [0 for x in arr]
# we now move from out to in storing the largest elements first and ending with the smallest, all while squaring our result
while index >= 0:
if abs(arr[left]) >= abs(arr[right]):
final[tracker] = arr[left] ** 2
left += 1
else:
final[tracker] = arr[right] ** 2
right -= 1
tracker -= 1
return final
Our new solution takes up the same auxiliary space, O(n), but we now have a solution that runs in O(n) time! Do you have another solution? Could you rewrite this solution with no need for auxiliary space? Post it below!
About Author
