JavaScript Algorithm: How to Square a Sorted Array

Guligena Aierken
Nov 13 · 2 min read
Image for post
Image for post
Photo by Hello I'm Nik 🎞 on Unsplash

Problem

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Example 2:

Note:

  1. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. A is sorted in non-decreasing order.

Solution

Brute Force

First, loop through the given array, and return the squared element. Like in example one, [-4, -1, 0, 3, 10] becomes [16, 1, 0, 9, 100]. After we squared all elements, we can use JavaScript array sort()method to sort the transformed array in-place in ascending order.

https://gist.github.com/GAierken/851844056ae45cbb1d3da04732f72fac

The time complexity of above solution is O(n log n), which is not ideal. How can we optimized the solution? The problem states that the given array is sorted in ascending order. Can we use it to improve the time complexity?

Two-Pointers

The sorted in ascending order given array makes it easy to see that by the absolute value, the largest numbers are at the beginning and the end of the given array, and values are decreasing to the middle. So we can consider two pointers approach. One from the start and one from the end.

https://gist.github.com/GAierken/f7dd2583c4419e5faa5de08110fe61ef

The time complexity of the two pointers is O(n).

JavaScript In Plain English

New JavaScript + Web Development articles every day.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store