How do you approach Squares of a Sorted Array?

Squaring then sorting works in O(n log n) - the follow-up asks for O(n).

What is the time complexity of Squares of a Sorted Array?

Time complexity: O(n) - single pass. Space complexity: O(n) - for the output array (O(1) extra).

What are common mistakes on Squares of a Sorted Array?

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample. Moving both pointers on a match when only one should move, which steps over valid pairs. Choosing left < right where left <= right is meant. The first never examines the middle element.

gitGood.dev

← Back to problems

Squares of a Sorted Array

EasyAlgorithms

Description

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Squaring a negative number makes it positive, so the smallest squares may come from the middle of the array. Try to solve it in O(n) time without sorting the squared values.

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]

Example 3

Input: nums = [1,2,3]

Output: [1,4,9]

Constraints

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

Squares of a Sorted Array: approach, complexity and pitfalls

An easy two pointers problem, graded against 7 test cases (4 of them hidden).

The pattern: Two Pointers

Two indices walking a sorted array or string, usually from opposite ends.

Reach for it when you see: A sorted input, a palindrome check, or a pair/triplet that must satisfy a condition.

If you are stuck

Show the 3-step hint ladder

Squaring then sorting works in O(n log n) - the follow-up asks for O(n).
The largest square is always at one of the two ends of the original array.
Use two pointers at the ends and fill the result array from the back with the larger square.

The optimal approach

Show the approach: Two Pointers Filling from the Back

Because the input is sorted, the largest absolute value (and therefore the largest square) is always at one of the two ends. Keep a pointer at each end, compare the squares, write the larger one into the last unfilled slot of the result array, and move that pointer inward.

Time: O(n) - single pass
Space: O(n) - for the output array (O(1) extra)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Two Pointers mistakes

These apply to the pattern as a whole, not just this problem.

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample.
Moving both pointers on a match when only one should move, which steps over valid pairs.
Choosing `left < right` where `left <= right` is meant. The first never examines the middle element.