Frontend School

Sorted Squares of an Array

DSA
medium

Sorted Squares of an Array

Medium
Two Pointers
Arrays
Sorting

Overview

Imagine you're building a feature for a financial analytics platform that needs to display the squared values of a series of stock price changes. These changes are naturally ordered (e.g., from lowest dip to highest peak), but squaring them can disrupt this order (e.g., -5 squared is 25, which is greater than 2 squared). Your task is to efficiently transform this sorted array of changes into an array of their squares, also sorted. This problem evaluates your ability to leverage data properties for optimal algorithmic design.

What you need to do / Task

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

Input & output

  • nums: An array of integers, sorted in non-decreasing order.
  • Return: A new array containing the squares of each number in nums, sorted in non-decreasing order.

Clarifications

  • nums can contain negative numbers, zeros, and positive numbers.
  • The length of nums can be zero (empty array). In this case, return an empty array.
  • The output array must also be sorted in non-decreasing order.

Examples

1

Example 1

Input:

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

Output:

[0,1,9,16,100]

Note:

The original array nums is [-4,-1,0,3,10]. Squaring each element gives [16,1,0,9,100]. Sorting this array results in [0,1,9,16,100]. The two-pointer approach avoids explicit sorting.

2

Example 2

Input:

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

Output:

[4,9,9,49,121]

Note:

Original: [-7,-3,2,3,11]. Squares: [49,9,4,9,121]. Sorted: [4,9,9,49,121].

3

Example 3

Input:

nums = [-2,0,1]

Output:

[0,1,4]

Note:

Original: [-2,0,1]. Squares: [4,0,1]. Sorted: [0,1,4].

Constraints

Constraints & assumptions

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

Out of scope

  • Handling non-integer inputs.
  • Optimizations for extremely large numbers that might exceed standard integer type limits (assume standard integer types are sufficient).

What interviewers evaluate

  • Correctness of the algorithm for all edge cases (empty array, all negative, all positive, mixed).
  • Efficiency of the solution in terms of time and space complexity.
  • Clear and concise code structure and variable naming.
  • Ability to articulate the two-pointer approach and its benefits.

Loading editor...