EasyArrayTwo PointersSorting

Squares of a Sorted Array

1 approach, code in every language

You receive an integer array already sorted in non-decreasing order. Produce a new array containing the square of every element, arranged from smallest to largest.

The challenge is that negative numbers can square into large values, so the largest squares live at the two ends of the input rather than in the middle.

Example 1

Input: nums = [-4, -1, 0, 3, 10]

Output: [0, 1, 9, 16, 100]

Squaring gives 16, 1, 0, 9, 100, which sorts into the shown result.

Example 2

Input: nums = [-7, -3, 2, 3, 11]

Output: [4, 9, 9, 49, 121]

The largest square, 121, comes from the rightmost value while 49 comes from the leftmost.

Constraints

1 ≤ nums.length ≤ 10^4
-10^4 ≤ nums[i] ≤ 10^4
nums is sorted in non-decreasing order

Two Pointers Filling From the Back

Compare the squares at both ends of the sorted input and drop the larger one into the result array from the last slot backward.

Loading animation…

Intuition

The biggest square must sit at one of the two extremes, because the array is sorted and the most negative and most positive numbers are farthest from zero. By keeping one pointer at each end and always taking whichever end has the larger square, we can fill the output array from the back toward the front. This produces a fully sorted result in one pass without ever calling a sort routine.

Algorithm walkthrough

1Allocate a result array of the same length and set a write position at its last index.
2Place left at the start and right at the end of the input.
3Compare the squares of nums[left] and nums[right].
4Write the larger square at the current write position and move the pointer it came from inward.
5Decrement the write position and repeat until the two pointers cross.

Implementation

from typing import List

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        left, right = 0, n - 1
        pos = n - 1
        while left <= right:
            left_sq = nums[left] * nums[left]
            right_sq = nums[right] * nums[right]
            if left_sq > right_sq:
                result[pos] = left_sq
                left += 1
            else:
                result[pos] = right_sq
                right -= 1
            pos -= 1
        return result

Time

O(n)

Space

O(n)

One linear pass fills the answer; the O(n) space is the required output array, not auxiliary bookkeeping.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Sorted Drift Energies is our own problem on the technique behind Squares of a Sorted Array: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free