100Days of Code #day 13

Today we are going back to a classic a leet code problem. For this problem in the first time in ever I came up with four approaches ( yeah four ). I will let on to the problem then.

Question : Given an non-empty integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Approach 1:

1. Square the numbers in the array.
2. Sort the squared numbers and return the array.

Though this approach consumes only O(1) space but the sorting takes O(n log n ) and the squaring will also take an O(n) time so in total it will take O(n+n log n) time

This is not the best approach so moving on

Approach 2:

1. Sorting the numbers irrespective of negative numbers i.e after sorting the array will look like [0,-1,3,-4,10]
2. And then square the numbers in array.

Okay this approach will also take the similar amount of time Moving on

Approach 3:

1. Square the numbers
2. While squaring store the same in a TreeSet(which will order the squared numbers itself)
3. Return the treeset converted into array

But rather than the additional space complexity of O(n) this approach might not work if the array has duplicates

Then, what can we do now. There is one point in the array question the array is sorted ( so the greatest negative values will be in the front and greatest positive values will be in the back ) Classical two pointer approach.

Approach 4:

1. Have two pointers one at the start and one at the end.
2. Populate the resultant array with the greater square value.
3. iterate until you reach the front.

Time Complexity : O(n) Space Complexity : O(n)

#100DaysofCode #Day13