---
###### tags: `Leetcode`
---
# Leetcode 977. Squares of a Sorted Array

[link](https://leetcode.com/problems/squares-of-a-sorted-array/)

---

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

#### Example 1:

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].

#### Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

#### Constraints:
- 1 <= nums.length <= 10^4
- -10^4 <= nums[i] <= 10^4
- nums is sorted in non-decreasing order.

---

題意: 給一個non-decreasing order array, 要你寫出按照各元素平方後由小到大排列的list

---

Here I used two pointers to compare the absolute values for the left element and the right element. We fill this list from the end. So, we have to fill it with the largest square first.

If the absolute of the right element is bigger than the absolute of the left element, then we store the squares of the right number into the new list, while doing so the pointers l and r are correspondingly incremented/decremented until l > r.

#### Solution 1

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        l, r = 0, len(nums) - 1
        res = [0] * len(nums)
        p = len(nums) - 1

        while l <= r:
            if abs(nums[l]) > abs(nums[r]):
                res[p] = nums[l] ** 2
                l += 1
            
            else:
                res[p] = nums[r] ** 2
                r -= 1
            
            p -= 1
        
        return res
        

O(T): O(n)
O(S): O(n)