Skip to main content

977. Squares of a Sorted Array

easy

Given a sorted array of integers (possibly negative), return a new sorted array containing each element squared. Two-pointer classic that beats the naive sort by an order in clock time.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

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

Examples

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 = [-5,-3,-2,-1]
Output
[1,4,9,25]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

The naive square-then-sort is O(n log n). Can the input's sorted order buy you something cheaper?

Hint 2

The largest absolute value sits at one of the two ends of the input. Where does the next-largest sit?

Hint 3

Walk two pointers inward from both ends, writing squares into the result array from the back to the front.

Solution approach

Reveal approach

Maintain two pointers: left at index 0 and right at index n-1. Allocate a result array of the same length and fill it from right to left. At each step compare the absolute values at left and right (or equivalently their squares); whichever is larger gets written to the current write position and that pointer moves inward. The key insight is that the largest square has to come from one of the two ends because the input is sorted, so picking from the outside and writing backward guarantees a sorted output in a single pass without an extra sort.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • two-pointers

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Facebook
  • Apple

Practice these live with InterviewChamp.AI

Drill Squares of a Sorted Array and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →