Coding: How to Square A Sorted Array In Python

Posted on Sep 28, 2020

The skills we demoed here can be learned through taking Data Science with Machine Learning bootcamp with NYC Data Science Academy.

LinkedInGitHubEmail | 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
            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

Related Articles

Leave a Comment

No comments found.

View Posts by Categories

Our Recent Popular Posts

View Posts by Tags

#python #trainwithnycdsa 2019 2020 Revenue 3-points agriculture air quality airbnb airline alcohol Alex Baransky algorithm alumni Alumni Interview Alumni Reviews Alumni Spotlight alumni story Alumnus ames dataset ames housing dataset apartment rent API Application artist aws bank loans beautiful soup Best Bootcamp Best Data Science 2019 Best Data Science Bootcamp Best Data Science Bootcamp 2020 Best Ranked Big Data Book Launch Book-Signing bootcamp Bootcamp Alumni Bootcamp Prep boston safety Bundles cake recipe California Cancer Research capstone car price Career Career Day citibike classic cars classpass clustering Coding Course Demo Course Report covid 19 credit credit card crime frequency crops D3.js data data analysis Data Analyst data analytics data for tripadvisor reviews data science Data Science Academy Data Science Bootcamp Data science jobs Data Science Reviews Data Scientist Data Scientist Jobs data visualization database Deep Learning Demo Day Discount disney dplyr drug data e-commerce economy employee employee burnout employer networking environment feature engineering Finance Financial Data Science fitness studio Flask flight delay gbm Get Hired ggplot2 googleVis H20 Hadoop hallmark holiday movie happiness healthcare frauds higgs boson Hiring hiring partner events Hiring Partners hotels housing housing data housing predictions housing price hy-vee Income Industry Experts Injuries Instructor Blog Instructor Interview insurance italki Job Job Placement Jobs Jon Krohn JP Morgan Chase Kaggle Kickstarter las vegas airport lasso regression Lead Data Scienctist Lead Data Scientist leaflet league linear regression Logistic Regression machine learning Maps market matplotlib Medical Research Meet the team meetup methal health miami beach movie music Napoli NBA netflix Networking neural network Neural networks New Courses NHL nlp NYC NYC Data Science nyc data science academy NYC Open Data nyc property NYCDSA NYCDSA Alumni Online Online Bootcamp Online Training Open Data painter pandas Part-time performance phoenix pollutants Portfolio Development precision measurement prediction Prework Programming public safety PwC python Python Data Analysis python machine learning python scrapy python web scraping python webscraping Python Workshop R R Data Analysis R language R Programming R Shiny r studio R Visualization R Workshop R-bloggers random forest Ranking recommendation recommendation system regression Remote remote data science bootcamp Scrapy scrapy visualization seaborn seafood type Selenium sentiment analysis sentiment classification Shiny Shiny Dashboard Spark Special Special Summer Sports statistics streaming Student Interview Student Showcase SVM Switchup Tableau teachers team team performance TensorFlow Testimonial tf-idf Top Data Science Bootcamp Top manufacturing companies Transfers tweets twitter videos visualization wallstreet wallstreetbets web scraping Weekend Course What to expect whiskey whiskeyadvocate wildfire word cloud word2vec XGBoost yelp youtube trending ZORI