{"id":2107,"date":"2020-09-28T23:03:25","date_gmt":"2020-09-28T23:03:25","guid":{"rendered":"https:\/\/data-science.gotoauthority.com\/2020\/09\/28\/squaring-a-sorted-array-in-python\/"},"modified":"2020-09-28T23:03:25","modified_gmt":"2020-09-28T23:03:25","slug":"squaring-a-sorted-array-in-python","status":"publish","type":"post","link":"https:\/\/wealthrevelation.com\/data-science\/2020\/09\/28\/squaring-a-sorted-array-in-python\/","title":{"rendered":"Squaring A Sorted Array In Python"},"content":{"rendered":"
\n
\"\"\"\"<\/figure>\n

Given a sorted list of integers, square the elements and give the output in sorted order.<\/h4>\n

Let’s take a look at a very straightforward solution first:<\/p>\n

def SortedSquares (arr):\n     # We will use list comprehension to square our list\n     temp = [x**2 for x in arr]\n\n     # Now that we have our list squared we can use the sorted function to return our answer\n\n     return sorted(temp)<\/code><\/pre>\n
While this solution is correct, it takes up additional space because the sorted function makes a copy of our original list. \u00a0This 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. \u00a0Additionally, this solution is relatively slow. \u00a0We 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). \u00a0Can we modify the solution to make it faster? \u00a0Yes!<\/p>\n
def SortedSquares (arr):\n     # 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\n\n     # let's start with two pointers, one at element [0] and one  at element [arr_length - 1]\n\n     left, right = 0, len(arr)-1\n     \n     # 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\n\n     tracker = len(arr) - 1\n     final = [0 for x in arr]\n\n     # we now move from out to in storing the largest elements first and ending with the smallest, all while squaring our result\n\n     while index >= 0: \n  \n        if abs(arr[left]) >= abs(arr[right]): \n            final[tracker] = arr[left] ** 2 \n            left += 1\n        else: \n            final[tracker] = arr[right] ** 2 \n            right -= 1\n        tracker -= 1\n      \n    return final \n\n     <\/code><\/pre>\n
Our new solution takes up the same auxiliary space, O(n), but we now have a solution that runs in O(n) time! \u00a0Do you have another solution? \u00a0Could you rewrite this solution with no need for auxiliary space? \u00a0Post it below!<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
https:\/\/nycdatascience.com\/blog\/student-works\/squaring-a-sorted-array-in-python\/<\/p>\n","protected":false},"author":0,"featured_media":2108,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[2],"tags":[],"_links":{"self":[{"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/posts\/2107"}],"collection":[{"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/types\/post"}],"replies":[{"embeddable":true,"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/comments?post=2107"}],"version-history":[{"count":0,"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/posts\/2107\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/media\/2108"}],"wp:attachment":[{"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/media?parent=2107"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/categories?post=2107"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/tags?post=2107"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}