DEV Community

Dhruvin
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]
Enter fullscreen mode Exit fullscreen mode

Sample Output

[1, 4, 9, 25, 36, 64, 81]
Enter fullscreen mode Exit fullscreen mode
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;
}
Enter fullscreen mode Exit fullscreen mode

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)

Collapse
jonrandy profile image
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)

Collapse
dhruvindev profile image
Dhruvin Author

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