https://leetcode.com/problems/squares-of-a-sorted-array

Note, that our numbers will look like this: first we have some negative numbers in increasing order (may be 0 of them) and then we have some positive numbers in increasing order (again may be 0 of them).

  1. Note, that if we have negative number in increasing order, then their squares will be in decreasing order, so we need to invert this part.
  2. If we have positive increasing numbers, then their squares also increasing numbers.
  3. Now we have two lists with increasing numbers and we need to creaty one list with increasing numbers, how we can do it? We can use merge sort and do it by hands. However it happens, that if we run the code as it is it will be O(n). Why? Because python uses so-called Timsort https://en.wikipedia.org/wiki/Timsort which will look for sorted patterns in data.

Complexity: time and space complexity is O(n).

class Solution:
    def sortedSquares(self, nums):
        return sorted([i**2 for i in nums if i > 0][::-1] + [i**2 for i in nums if i <= 0])

If you like the solution, you can upvote it on leetcode discussion section: Problem 0977