How do you solve Squares of a Sorted Array?

Initialize two pointers at the start and end of the input array. Create an output array of the same size. Iterate from the end of the output array backward, at each step comparing the squares of the elements at the two pointers. Place the larger square at the current output position and move the corresponding pointer inward. Continue until all positions are filled, achieving O(n) time and O(n) space.

Squares of a Sorted Array

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

O(n). Each element is visited exactly once by either the left or right pointer, and each comparison and assignment is O(1), resulting in a linear time complexity.

Q: What pattern does Squares of a Sorted Array use?

The Pattern: Two Pointers (Greedy Contraction) The Heuristic: The largest squared values must come from the ends of the sorted array, so by comparing and placing the larger square at the end of the output array and moving pointers inward, the algorithm efficiently constructs the sorted squares in a single pass.

Easy Two Pointers

Problem

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

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

Example

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

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

The brute-force approach squares every element and then sorts the array, which takes O(n log n) time and ignores that nums is already sorted. The optimal method uses two pointers at the ends of the array and fills the result from the back: - Start: l = 0 (value -7, square 49), r = 4 (value 11, square 121). Place 121 at ans[4], move r to 3. - Next: l = 0 (square 49), r = 3 (value 3, square 9). Place 49 at ans[3], move l to 1. - Next: l = 1 (value -3, square 9), r = 3 (value 3, square 9). Squares tie, place 9 at ans[2], move r to 2. - Continue this process, placing the larger square at ans[i] and moving the corresponding pointer inward, until l > r. By always writing the largest remaining square at the current back position, the output array becomes [4, 9, 9, 49, 121] in O(n) time without an extra sort.

Approach

Straightforward Solution

Square all elements and sort the resulting array. This approach takes O(n log n) time due to sorting and does not leverage the input's sorted property.

Core Observation

The squares of a sorted array are not necessarily sorted because negative numbers become positive. However, the largest squared values must come from either end of the array since the array is sorted.

Path to Optimal

Preview

Recognizing that the largest squares come from the array's ends, a two-pointer approach can be used…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize two pointers at the start and end of the input array. Create an output array of the same size…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each element is visited exactly once by either the left or right pointer, and each comparison and assignment is O(1), resulting in a linear time complexity.

Space

O(n)

An output array of size n is created to store the sorted squares. This auxiliary space is necessary since the output must be returned separately from the input.

Pattern Spotlight

Two Pointers (Greedy Contraction)

The largest squared values must come from the ends of the sorted array, so by comparing and placing the larger square at the end of the output array and moving pointers inward, the algorithm efficiently constructs the sorted squares in a single pass.

Solution

Python

1class Solution:
  def sortedSquares(self, nums: List[int]) -> List[int]:
      n = len(nums)
      ans = [0] * n
5
      l, r = 0, n - 1      
      i = n - 1            
8
      while l <= r:
          left_sq = nums[l] * nums[l]
          right_sq = nums[r] * nums[r]
12
          if left_sq > right_sq:
              ans[i] = left_sq
              l += 1
          else:
              ans[i] = right_sq
              r -= 1
19
          i -= 1
21
      return ans

Step-by-Step Solution

Initialize Pointers and Output Array

3n = len(nums)
4ans = [0] * n
6l, r = 0, n - 1      
7i = n - 1            

Objective

To set up the two pointers at the start and end of the input array and prepare the output array to store results.

Key Insight

Starting pointers at both ends leverages the sorted property of the input array. The output array is preallocated to avoid dynamic resizing and to allow filling from the end, which matches the order of largest squares found.

Interview Quick-Check

Core Logic

Two pointers at the array boundaries allow simultaneous comparison of the largest magnitude elements, which after squaring, produce the largest values.

State & Boundaries

The output array is indexed from the end to the start, matching the order in which the largest squares are placed.

Common Pitfalls & Bugs

Forgetting to initialize the output array with the correct size or incorrect pointer positions can lead to index errors.

Compare Squares and Fill Output Array from End

To iteratively compare squares at the left and right pointers, place the larger square at the current output index, and move pointers inward accordingly.

Return the Sorted Squares Array

To return the fully populated output array containing the squares in sorted order.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 13 Critical

if left_sq > right_sq:

Compare the left and right squares to decide which is larger.

This comparison identifies the larger square to place at the current output index, ensuring the output array is sorted.

Full line-by-line criticality + rationale for all 15 lines available on Pro.

Test Your Understanding

Why does the two-pointer approach fill the output array from the end rather than from the start?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Squares of a Sorted Array from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Squares of a Sorted Array drill

or drill a free problem

1	`class Solution:`
2	`def sortedSquares(self, nums: List[int]) -> List[int]:`
3	`n = len(nums)`
4	`ans = [0] * n`
5
6	`l, r = 0, n - 1`
7	`i = n - 1`
8
9	`while l <= r:`
10	`left_sq = nums[l] * nums[l]`
11	`right_sq = nums[r] * nums[r]`
12
13	`if left_sq > right_sq:`
14	`ans[i] = left_sq`
15	`l += 1`
16	`else:`
17	`ans[i] = right_sq`
18	`r -= 1`
19
20	`i -= 1`
21
22	`return ans`

3	`n = len(nums)`
4	`ans = [0] * n`
6	`l, r = 0, n - 1`
7	`i = n - 1`