EasyArrayTwo PointersSortingUpdated Sep 2026

977. Squares of a Sorted Array

Asked at Meta, Uber

Difficulty

Easy

Time

O(n)

Space

O(n)

Pattern

Array

Companies

2

Problem

You are given an integer array nums that is already sorted in non-decreasing order (smallest to largest). Return a new array that holds the square of every number in nums, also sorted in non-decreasing order.

The input may contain negative numbers, so squaring can change the order: a very negative number becomes a very large positive number. For example, -4 squares to 16, which is bigger than 3^2 = 9.

The easy way is to square everything and then sort, which costs O(n log n). The follow-up asks for an O(n) solution that uses the fact that the input is already sorted.

Squaring can flip the order

nums-4-1031001234Input is sorted, but -4 and 10 are the two extremessquares1610910001234After squaring, 16 sits at the front and 100 at theback — not sortedanswer0191610001234Sorted squares: the two extremes become the twolargest values
The most negative value and the largest positive value both produce the biggest squares, so the answer is built from the outside in.

Constraints

  • ●1 <= nums.length <= 10^4
  • ●-10^4 <= nums[i] <= 10^4
  • ●nums is sorted in non-decreasing order

Examples

Example 1
Inputnums = [-4,-1,0,3,10]
Output[0,1,9,16,100]
WhySquaring gives 16, 1, 0, 9, 100. Sorting those values from small to large gives 0, 1, 9, 16, 100.
Example 2
Inputnums = [-7,-3,2,3,11]
Output[4,9,9,49,121]
WhySquaring gives 49, 9, 4, 9, 121. After sorting: 4, 9, 9, 49, 121.

Asked At

2 companies
CompanyDifficulty
MetaEasyView all Meta questions →
UberEasyView all Uber questions →

How to Think About It

1

Naive: square every element, then sort. O(n log n). The sorted property allows O(n).

2

Key insight: the largest squares come from the most negative numbers (left end) or the largest positive numbers (right end). Compare absolute values from both ends.

3

Use two pointers from both ends. Compare nums[left]^2 vs nums[right]^2. Place the larger one at the end of the result array and move that pointer inward.

4

Why it works: in a sorted array, the extremes have the largest absolute values. Squaring preserves the order of absolute values. By filling the result from right to left, you avoid sorting.

5

Edge cases: all negative, all positive, mixed, single element, zeros.

Optimal Approach

Step 1: Set left = 0, right = n-1. Create result array of size n.
Step 2: For position i from n-1 down to 0:
If |nums[left]| > |nums[right]|: result[i] = nums[left]^2, left++
Else: result[i] = nums[right]^2, right--
Step 3: Return result.

You fill the result from the largest position down to 0. Each step places the next largest square.

Time: O(n) — single pass. Space: O(n) for the result.

Two pointers, fill from the right

nums-4-1031001234leftrightStart: left at -4, right at 10. |10| > |-4|, so 100goes to result[4].nums-4-1031001234leftrightright moved to 3. |-4| > |3|, so 16 goes to result[3]and left moves to -1.nums-4-1031001234leftrightNow |3| > |-1|, so 9 goes to result[2]; then |−1| >|0|, so 1 goes to result[1].result[i] = max(nums[left]^2, nums[right]^2)move the pointer you used inwardfill i from n-1 down to 0
Compare the absolute values at both ends, take the bigger square, and place it at the current last free slot.
ComplexityTime O(n)Space O(n)One pass with two pointers fills the result; the extra space is just the output array.

What Trips People Up in Real Interviews

1

Sorting after squaring. That's O(n log n). The two-pointer approach is O(n) and is the expected solution.

2

Comparing squared values instead of absolute values. Squaring can overflow for large negative numbers. Compare abs() values instead.

3

Filling the result from left to right. You must fill from right to left because the largest squares are at the extremes.

4

Not handling the case where both pointers meet. When left == right, place the last element and stop.

5

Using a priority queue or heap. While it works in O(n log n), the two-pointer approach is simpler and faster.

Solution Code

O(n) time
def sortedSquares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    for i in range(n - 1, -1, -1):
        if abs(nums[left]) > abs(nums[right]):
            result[i] = nums[left] ** 2
            left += 1
        else:
            result[i] = nums[right] ** 2
            right -= 1
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Squares of a Sorted Array problem?

Given an integer array sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order. The two-pointer approach achieves `O(n)` time without sorting.

How do you solve Squares of a Sorted Array?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Squares of a Sorted Array?

Squares of a Sorted Array is asked at Meta, Uber. It is a easy difficulty problem.

What are common mistakes on Squares of a Sorted Array?
  • Sorting after squaring. That's `O(n log n)`. The two-pointer approach is `O(n)` and is the expected solution.
  • Comparing squared values instead of absolute values. Squaring can overflow for large negative numbers. Compare `abs()` values instead.
  • Filling the result from left to right. You must fill from right to left because the largest squares are at the extremes.
  • Not handling the case where both pointers meet. When left == right, place the last element and stop.
  • Using a `priority queue` or `heap`. While it works in `O(n log n)`, the two-pointer approach is simpler and faster.