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