20. Squares of a Sorted Array
Square every input value and return the squares in sorted order. The input may contain negative numbers, whose squares can be larger than those of nearby positive values.
Keep every occurrence and leave the input unchanged. Use the numeric representation required by the contract so squaring a large integer does not silently overflow.
Example 1
Input
[-7,-3,2,3,11]
Output
[4,9,9,49,121]
Explanation: The largest remaining magnitude is always at an endpoint.
Example 2
Input
[-2147483648,0,2147483647]
Output
[0,4611686014132420609,4611686018427387904]
Explanation: Both large squares are represented exactly by Java long.
Constraints
0 <= nums.length <= 105-231 <= nums[i] <= 231 - 1- nums is sorted in nondecreasing order. Return sorted squares in a new array.
Hints
Hint 1
Where can the greatest absolute value of a sorted interval occur?
Hint 2
Which output position should receive its square?
Hint 3
Compare endpoint long squares and fill from the last output position.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Fill the largest squares backwards
[-7,-3,2,3,11]
[4,9,9,49,121]