Hello, my comrades, Leo here. The day has come and we are solving the Squares of a Sorted Array in Swift.
We’ll continue the algorithm series by solving a classic Two Pointer technique.
So let’s go to the problem.
The problem
You have a list of sorted integers and you want to create a function 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 reduces 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 falls apart. But how can we solve this now?
The two-pointers and Squares of a Sorted Array in Swift
Like a lot of other array problems, we have to create two-pointers. The idea of this solution is to divide the array into 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 the 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 at the beginning of the new structure 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 the 2 mark, we iterate over the list comparing all the values until the leftPointer is greater than the rightPointer. On 3 it’s where the magic happens, we compare the square of each side of the list, and depending on which one is greater we insert it into the first position in the answer list.
The mark 4 is necessary because we are appending from the highest to the lowest in the answer array, we could just append in position zero every time but… I thought that would be more confusing.
And we are 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.
Algorithms: Continue Studying
You might be asked in your interview to solve a linked list problem, if that happens high are the chances to merge linked lists. In this article, we will explore how you can do that in Swift.
Dynamic programming can be really tough if you don’t practice, actually even if you practice is not an easy topic to tackle. The good thing is that you can start your dynamic programming studies with this article where we solve the longest nonadjacent subsequence and do really well in your interviews.
Summary – Squares of a Sorted Array in Swift
Today we solved a classic two-pointer problem with a very simple approach. I hope you enjoy this and if you have any comments or feedback please share below.
That’s all my people, I hope you liked reading this article as much as I enjoyed writing it. If you want to support this blog you can Buy Me a Coffee or leave a comment saying hello. You can also sponsor posts and I’m open to freelance writing! You can reach me on LinkedIn or Twitter and send me an e-mail through the contact page.
Thanks for reading and… That’s all folks.
