# 977. Squares of a Sorted Array

[](https://hackmd.io/tGWc1byfTwy_anosvUftsg)

###### tags: `Leetcode`

Source: [:link:][leetcode link]

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

Average Rating：:star::star::star::star:

## Question Description

:::info
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.

:star: **Follow up:** Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

## Question Explanation

***English Version***

Personally speaking, this question might be difficult for C++ and Java users. As for Python, we have functions like `sort` and `sorted`, which help to sort the list automatically.

:::danger
Note: the time complexity might become the issue.
:::

So, the Python solution 1 is a brute force method. In order to decrease the complexity from `O(n + nlogn)` to `O(n)`, we perhaps have to use two-pointers approach.

:pushpin:*Algorithm:*

Remember that the array was sorted in **non-decreasing order**

* Two pointers`i` and `j` where i points to the beginning of the array, then `j` points to the tail of the array.
* Compare two values `|[i]|` and `|[j]|`
* Put the larger value's square to the tail of the
+ Or compare their square directly
* Then update from the tail to the head

***Chinese Version***

考虑==双指针法==，`i`指向起始位置，`j`指向终止位置。

定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

如果`A[i] * A[i] < A[j] * A[j] `那么`result[k--] = A[j] * A[j]`

如果`A[i] * A[i] >= A[j] * A[j]` 那么`result[k--] = A[i] * A[i]`

## Code

Python1:

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        for index, item in enumerate(nums):
            nums[index] = item*item
        nums.sort(reverse = False)
        return nums

But the time complexity will become `O(n + nlogn)`

Python2

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted(i * i for i in nums)

Same as Python1

:::success
Python3 Two pointers approach

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        i,j,k = 0,n - 1,n-1
        new_array = [-1] * n  #used to store the answer
        while i <= j:
            x = nums[i]**2
            y = nums[j]**2
            if x > y:   #head value^2 > tail^2, so store head^2 in the tail of the new array
                new_array[k] = x  #store the value from tail to head
                i += 1  #then compare the second head value with the tail 
            else:
                new_array[k] = y
                j -= 1   #note: which value has been stored in the new array, it will be passed for the next round
            k -= 1
        return new_array

This will lead to a time complexity of **O(n)**

:::

## Linked Questions

* 360.Sort Transformed Array
* 88. Merge Sorted Array

## Q&A

N/A