Two Pointers Pointers from both ends
158. Squares of a Sorted Array
You are given an array of integers nums sorted in non-decreasing order. Return a new array that holds the
square of every element of nums, also sorted in non-decreasing order.
Non-decreasing means that each element is greater than or equal to the one before it, so a value can appear
more than once. The answer has the same length as nums, and every square appears as many times as it is
made.
Example 1
Input: nums = [-7, -3, -1, 2, 4, 8]
[1,4,9,16,49,64]Explanation: The squares in the order of nums are 49, 9, 1, 4, 16 and 64. Sorted, they are [1,4,9,16,49,64].
Example 2
Input: nums = [-9, -5, -5, 0]
[0,25,25,81]Explanation: No element is positive, so the squares come out in the reverse order of nums. Both −5s give 25, and
both copies stay.
Example 3
Input: nums = [-1000000000, 3, 1000000000]
[9,1000000000000000000,1000000000000000000]Explanation: Both 109 and −109 square to 1018, which is far more than a 32-bit integer can hold.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-109 ≤ nums[i] ≤ 109numsis sorted in non-decreasing order.
Clarifying questions
What you would ask an interviewer before writing any code.