## Leetcode977

## Example,

Input: [-4,-1,0,3,10]

Output: [0,1,9,16,100]

## Solution 1: Square all the values and then sort the list

time complexiity: O(nlogn)

space complexity: O(n) | O(1) if we can modify same array using A.sort()

runtime: 228 ms | faster than 85.04% submissions

memory: 15 MB

1 | def sortedSquares(self, A: List[int]) -> List[int]: |

## Solution 2: Two pointers from each side, compare the squared values and add the larger value to a new list. Reverse the list at the end.

time complexiity: O(n)

space complexity: O(n)

runtime: 244 ms | faster than 57.48%

1 | def sortedSquares(self, A: List[int]) -> List[int]: |

## Solution 3: Two pointers from each side of array, compare the squared values, then add the larger value fron the back to the front of a predefined empty list

time complexiity: O(n)

space complexity: O(n)

runtime: 236 ms | faster than 72.37%

memory: 14.9 MB

1 | def sortedSquares(self, A: List[int]) -> List[int]: |

## My takeaway,

It’s interesting to know that built in functions with the worst time complexity actually run much faster than optimized solution.