Sorted Squared Array

Hello!

In this task, the input is given a sorted list, and the goal is to create a new list that will contain the squared sorted numbers from the first list. The simplest solution would be to loop through the first list, square all the numbers, add to our new list, and sort. But this solution will not be optimal.

Let’s consider a more optimal solution that will run linearly.

For example, take the following input list - [-9, -1, 2, 3, 5, 6]

To solve this problem in linear time, we use two pointers that will indicate the beginning and end of the list. We also need a variable that will indicate where in the new list we need to insert a number. Initially, it will be len (array) - 1 because we will find the square of the largest number and add it to the end of the list.

func SortedSquaredArray(array []int) []int {
    result := make([]int, len(array))
    leftIdx := 0
    rightIdx := len(array) - 1
    pos := len(array) - 1
}

As a helper which will calculate absolute value. The math package has such a function. But it only accepts float64. So let’s create our own

func Abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Now when everything is ready, we need to create a loop that will work until the left pointer is equal to the right. In the loop, we will check whether the list item with the index rightIdx is larger than leftIdx. If the condition is met, we count the square of the number under the index rightIdx and write it to the list result [pos] = array [rightIdx] * array [rightIdx], rightIdx we need to reduce by one to go to the next element in list on the from the right side. If the condition is not met, it means that the number from the list under leftIdx is larger, so we need to write it to the list result [pos] = array [leftIdx] * array [leftIdx] and we need to increase leftIdx by one, to go to the next list item on the left side. And at the end value of pos must also be reduced by one to write the new number in the correct place in the list.

func SortedSquaredArray(array []int) []int {
    result := make([]int, len(array))
    leftIdx := 0
    rightIdx := len(array) - 1
    pos := len(array) - 1

    for leftIdx <= rightIdx {
        if Abs(array[leftIdx]) < Abs(array[rightIdx]) {
            result[pos] = array[rightIdx] * array[rightIdx]
            rightIdx -= 1
        } else {
            result[pos] = array[leftIdx] * array[leftIdx]
            leftIdx += 1
        }
        pos -= 1
    }
 return result
}

If we call this method, we get the result [1, 4, 9, 25, 36, 81]