This content originally appeared on DEV Community and was authored by Dhruvin
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
- Add to new array
- 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 --
}
}
return toReturn;
}
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
This content originally appeared on DEV Community and was authored by Dhruvin
Dhruvin | Sciencx (2022-06-24T07:15:06+00:00) Crushing Job Interviews(DSA) – Sorted Squared Arrays. Retrieved from https://www.scien.cx/2022/06/24/crushing-job-interviewsdsa-sorted-squared-arrays/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.