# 977 Squares of a Sorted Array

## 1. Description

Given an integer array `nums`

sorted in **non-decreasing** order, return *an array of the squares of each number sorted in non-decreasing order*.

Constraints:

- \(1 \leq nums.length \leq 10^{4}\)
- \(-10^{4} \leq nums[i] \leq 10^{4}\)
`nums`

is sorted in**non-decreasing**order.

### 1.1. Examples:

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]. Input: nums = [-7,-3,2,3,11] Output: [4,9,9,49,121]

## 2. Solution

### 2.1. Understanding the problem

If \(e \geq 0, \forall e \in nums\), then the problem is trivial as we only need to square each element and the resulting array is already sorted.

We need to consider the case where negative integers are present.

I think the basic idea is that we can start from both ends of the squared list, and move towards the center of the list.
For example, we have the following list `[-2, -1, 0, 3, 10]`

, and its squared list `num_sq = [4, 1, 0, 9, 100]`

.
In general, we don't know if `num_sq[0] > num_sq[-1]`

or the other way around, but we **do know** that `num_sq`

is first **non-increasing** and then **non-decreasing**.

### 2.2. Algorithm

The basic algorithm following previous section is the following:

- We start with
`left_idx = 0`

and`right_idx = len(num_sq)-1`

and get`num_sq[left_idx]`

and`num_sq[right_idx]`

and compare them.- if
`num_sq[left_idx] <= num_sq[right_idx]`

, then we put`num_sq[left_idx]`

in the result list, and`left_idx += 1`

. - else we do the opposite.

- if
- Then we repeat the process until
`left_idx > right_idx`

.

### 2.3. Code

def sortedSquares(nums): """ :type nums: List[int] :rtype: List[int] """ ret = [] left_idx, right_idx = 0, len(nums) - 1 while left_idx <= right_idx: left_val = nums[left_idx] ** 2 right_val = nums[right_idx] ** 2 if left_val > right_val: ret.append(left_val) left_idx += 1 else: ret.append(right_val) right_idx -= 1 # we use append so the order is reversed, i.e. order is non-increasing # therefore need to reverse the list return ret[::-1] # tests nums = [0] result = [0] print(sortedSquares([0]) == [0]) nums = [0, 1] result = [0, 1] print(sortedSquares(nums) == result) nums = [-1, 0, 1] result = [0, 1, 1] print(sortedSquares(nums) == result) nums = [-2, -1, 0, 1] result = [0, 1, 1, 4] print(sortedSquares(nums) == result)

True True True True

#### 2.3.1. Complexity

##### 2.3.1.1. Time complexity:

`O(n)`

##### 2.3.1.2. Space complexity:

`O(n)`

for the resulting list.

### 2.4. Leetcode solution

`nil`

. Same algorithm.

```
<<imports for typing>>
```

#### 2.4.1. Time complexity:

#### 2.4.2. Space complexity:

## 3. More analysis

### 3.1. General thoughts

This is not too hard a question for someone who's never seen it before. I guess with Leetcode there's some clue as it's categorised as a Two Pointer question. So naturally one would think about starting from both ends of the list.