## DEV Community is a community of 890,060 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Dhruvin

Posted on

# Crushing Job Interviews(DSA) - Sorted Squared Arrays

### The Question

##### Difficulty: Kind of Medium

Write a function that takes in a non-empty array of integers that are sorted in ascending order and returns a new array of the same length with the squares of the original integers also sorted in ascending order.

Sample Input

``````array = [1, 2, 3, 5, 6, 8, 9]
``````

Sample Output

``````[1, 4, 9, 25, 36, 64, 81]
``````
##### Optimal Space & Time Complexity:

O(n) time | O(n) space - where n is the length of the input array

### The Thinking

It's important to ask your interviewer that can you mutate the original array given to you or you have to create a duplicate array.

So there are two way's to solve this, first is :

• Iterate through the array
• Square each number, and
• Sort the array

This solution is simple but the we can do better.

In the second solution, we use pointers.

P.S: Pointers in arrays context are used to keep track of the position while iterating through it.

So what we will do is:

• Iterate through the array,
• Keep track of the first and the last position of the array using pointers,
• Compare the absolute value of the items the pointers are pointing at.
• IF the first index value is greater, then place that value at the index we are iterating through in the duplicate array we created and increment the first pointer by 1.
• ELSE, place the other pointer arrays value at the current index we are iterating through and decrease the second pointer by 1.

Sounds Confusing ? Well it is, but I'm sure you'll get a better understanding by looking at code once. I'll not be writing down the first solutions since it's very simple and I believe you can easily come up with the solutions. But if you still want it, drop down a comment and I'll post it.

### The Solution (2nd one)

``````function sortedSquaredArray(array) {
const toReturn = [...array]
let smallerValueIdx= 0
let largerValueIdx = (array.length) - 1
for (let idx = array.length - 1; idx >=0; idx--) {
const smallerVal = array[smallerValueIdx]
const largeVal = array[largerValueIdx]

if (Math.abs(smallerVal) > Math.abs(largeVal)) {
toReturn[idx] =smallerVal * smallerVal
smallerValueIdx++
}
else{
toReturn[idx] = largeVal * largeVal
largerValueIdx --
}
}
}
``````

Got any doubt's ? Got a better solutions ? Drop a comment below and let's start a discussion.

Follow me on instagram for more awesome content on coding: https://www.instagram.com/dhruvindev

## Discussion (2)

Jon Randy

Am I missing something? You don't need to sort the final array if the initial array was already sorted (unless it contained negative values, but you problem definition does not mention this in any way)

Dhruvin

correct, the issues is negative values, I'm working to include multiple next next post onwards. Sorry for the misunderstanding on this one