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