Squares of a Sorted Array [leetcode easy]

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
2
def sortedSquares(self, A: List[int]) -> List[int]:
return sorted([i*i for i in A])

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def sortedSquares(self, A: List[int]) -> List[int]:
i = 0
j = len(A) - 1
result = []

while i <= j:
left = A[i]*A[i]
right = A[j]*A[j]

if left > right:
result.append(left)
i += 1
else:
result.append(right)
j -= 1

return result[::-1]

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def sortedSquares(self, A: List[int]) -> List[int]:
i = 0
j = len(A) - 1
result = [0]*len(A)
resultIndex = len(result) - 1

while i <= j:
left = A[i]*A[i]
right = A[j]*A[j]

if left > right:
result[resultIndex] = left
i += 1
else:
result[resultIndex] = right
j -= 1

resultIndex -= 1

return result

My takeaway,

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