### View *Squares of a Sorted Array* on LeetCode

## Statistics

**Time Spent Coding**

1 minute

**Time Complexity**

O(n) - At most, 2 * n elements are visited, but since a constant multiple of n does not increase the growth rate, the final time complexity is O(n).

**Space Complexity**

O(n) - A new list with n elements is created and then mutated into the final result, taking O(n) extra space.

**Runtime and Memory**

*Due to the small dataset that LeetCode uses to test the program, the trivial solution is “more optimal.”*

## Explanation

*The comments explain the program*

## Algorithm Used

**Two Pointer Algorithm -** An algorithm typically used to search a list where opposite ends of the list share a relationship that will be compared to determine some outcome.

For this problem, that condition would be identifying which negative numbers (if any) will result in a larger squared value.

**Visual Examples**

The two-pointer algorithm being performed on a list where the condition summing to 6, click to view

## Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
squares = [None] * len(nums)
left, right = 0, len(nums) - 1
# Increment from n to 0; this allows the numbers to be sorted in increasing order
for i in range(len(nums)-1,-1,-1):
# To accommodate for negative numbers, take the absolute values of both ends
# If the left number is larger, replace squares[i] with the left number and increment left
if abs(nums[left]) > abs(nums[right]):
squares[i] = nums[left] ** 2
left += 1
# Similarly, do this with the right when it is the largest number
else:
squares[i] = nums[right] ** 2
right -= 1
return squares