Algorithms: Squares of a Sorted Array in Swift

Swift Algorithms Series - Two Pointer Technique

Subscribe to my newsletter and never miss my upcoming articles

Hello my comrades, Leo here.

Today we'll continue the algorithm series solving a classic Two Pointer technique. So let's go to the problem . The image is

The problem

You have a list of sorted integers and you want to create a func that returns the square of that list sorted in ascending order. Ex: With [-5,-3,-2,0,1,6] the output would be: [0, 1, 4, 9, 25, 36]

At first sight this problem isn't very difficult, if consider only positive numbers. You could easily solve doing this FP reduce magic:

let sortedList2 = [0,1,2,5,6,8,10]
print(sortedList2.reduce(into: [Int]()) { result, value in
    result.append(value * value )
})

Generating the result: [0, 1, 4, 25, 36, 64, 100]

But if we consider that the input array could have negative numbers too, our pretty functional programming solution fall apart. But how can we solve this now?

The two pointers

Like a lot of others arrays problems we have to create two pointers. The idea of this solution is to divide the array in two parts, the negative one and the positive one and do an insertion-like sort in a third structure.

So with the two pointer solution you can just point one to end of the list ( aka the last positive integer) and the other to the first item of the list ( aka possible most negative number) and compare each other. The highest value you will insert in the beginning of the a new structure because it will be always the greater of the two pointers that you need to put there, and it's done. Simple right?

func sortedSquares(_ nums: [Int]) -> [Int] {
    var answer = [Int]()
    var leftPointer = 0 //1
    var rightPointer =  nums.count - 1 //1

    while leftPointer <= rightPointer { //2
        if (nums[leftPointer] * nums[leftPointer] > nums[rightPointer] * nums[rightPointer]) { //3
            answer.append(nums[leftPointer] * nums[leftPointer])
            leftPointer += 1
        } else {
            answer.append(nums[rightPointer] * nums[rightPointer])
            rightPointer -= 1
        }
    }
    return answer.reversed() //4
}

At 1 mark we create the pointers, each one pointing to the beginning and the end of the list. On 2 mark we iterate over the list comparing all the values until the leftPointer are greater than the rightPointer. On 3 it's where the magic happens, we compare the square of each side of the list and depending which one is greater we insert on the first position in the answer list.

And it's done!

Time and Space Complexity

The time complexity is O(N), because we traverse the initial list only one time. Edit: As suggested by Eduardo Tolmasquim, if we insert with append in the new list which is O(1) ( on average) and reverse the list after (mark 4, and it's O(1) too), we can get the total complexity of O(N). Thanks for the update!

The space complexity is O(N) too because weren't doing an in-place algorithm for this solution and we are using the same memory (N) as the input to create a new result structure.

Conclusion

Today we solved a classic two pointer problem with a very simple approach. I hope you enjoy this and if you have any comment or feedback please share below.

Thanks for the reading and... that's all folks.

credits: image

No Comments Yet