# Squaring A Sorted Array In Python

#### 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!

### Daniel Brancusi

View all posts by Daniel Brancusi >