Review the fundamentals: Arrays guide and time complexities.
Sorted Squares — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Sorted Squares problem optimally.
O(N)O(N)Problem Description
You are given an array of integers, nums, which is already sorted in non-decreasing order. Your task is to generate and return a new array containing the squares of each element from nums, also arranged in non-decreasing order.
Because the original sequence may contain negative numbers, the largest squared values can originate from either the extreme negative numbers at the beginning of the array or the extreme positive numbers at the end. Your solution should handle this distribution efficiently to construct the sorted result in $O(N)$ time complexity.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Sorted Squares"
WHY DOES IT MATTER?
The Two-Pointer converging strategy is a foundational pattern for array manipulation. It demonstrates how to exploit structural invariants (such as monotonic sorting or symmetry) to reduce $O(N \log N)$ search or sorting algorithms down to $O(N)$ linear time.
OPTIMIZATION CHALLENGE
The challenge is resisting the temptation to square first and sort later. Recognizing that extreme values live at extreme indices allows us to construct the output backwards in $O(N)$ time.
REAL-WORLD CONNECTION
In database engines and time-series analytics, metrics are often recorded as signed deviations from a baseline (e.g., temperature changes or stock yield deltas). When querying for extreme variance or magnitude, transforming and sorting these metrics efficiently relies on two-pointer techniques on pre-sorted indices to avoid full table rescans.
Whenever an array is sorted and you apply an even power function or absolute value transformation, think 'outer boundaries first'. Always attempt to fill the result array from largest to smallest to keep boundary logic clean.
COMPLEXITY AT A GLANCE
O(N)O(N)Core Theory — Why This Approach?
When an array of real numbers is sorted in non-decreasing order, the numbers themselves are monotonically increasing. However, applying the square function $f(x) = x^2$ breaks this linear monotonicity because $f(x)$ is a symmetric parabolic function centered at $x = 0$. Large negative numbers become large positive squares, while small negative numbers become small positive squares. Consequently, after squaring, the values form a 'V-shape' relative to their original position: the smallest squared values cluster around zero, while the largest squared values reside at the extreme left (most negative) and extreme right (most positive) ends of the array.
A naive strategy ignores the original sorted property, squares all elements sequentially, and runs a standard $O(N \log N)$ comparison sort. This is suboptimal because it discards the structural information already present. The key to an optimal solution lies in recognizing that the array is effectively composed of two sorted sequences merged together: the negative half (which becomes decreasing when squared) and the non-negative half (which remains increasing when squared).
Instead of finding where the negatives flip to positives and performing a standard two-way merge from the inside out, we can leverage the parabolic nature from the outside in. By placing two pointers at the boundary extremes—one at index $0$ and one at index $N-1$—we are guaranteed that the absolute maximum squared value of the entire array is located at one of these two positions. Thus, we can deterministically place elements into our result array from right to left (largest to smallest) in a single linear pass, achieving $O(N)$ time complexity.
Interview Questions on This Problem
Q1Why is building the result array from right-to-left (largest to smallest) computationally preferable to starting from the middle zero-point?
Starting from the extreme ends ($0$ and $N-1$) allows us to immediately identify the maximum elements without first finding the inflection point where negative numbers transition to non-negative numbers. Searching for the zero pivot requires $O(\log N)$ or $O(N)$ time, followed by careful handling of array bounds during an outward expansion. Constructing from right-to-left handles all negative, positive, or mixed configurations uniformly without edge-case checks for empty positive or negative partitions.
Q2Can this problem be solved in $O(N)$ time with $O(1)$ auxiliary space if modifying the input array is permitted?
Not easily within standard array representations. Squaring elements in-place corrupts the original values needed for relative absolute comparisons. While one could store both the original and squared values using bit manipulation or mathematical encoding (e.g., $arr[i] = original + squared \times MAX$), reordering them in-place in $O(N)$ time without $O(N)$ additional memory is equivalent to in-place merging of two sorted sub-arrays, which generally requires complex $O(N)$ algorithms with high constant factors. Thus, $O(N)$ auxiliary space for a new output array is standard and optimal.
Q3How would you adapt this algorithm if the input array was extremely large and stored across multiple distributed log files sorted by absolute value?
If inputs are already sorted by absolute value, the squared output order directly matches the input order, allowing a simple parallel mapping step $f(x) = x^2$ without any re-sorting. If they are sorted by signed values across partitions, each partition can compute its local boundary candidates, and a distributed two-pointer or k-way merge reduction can pull the largest values to build the global output sequence seamlessly.
Examples
Input
nums = [-7, -3, 0, 2, 5, 8]
Output
[0, 4, 9, 25, 49, 64]
Explanation: Squaring each number gives: [49, 9, 0, 4, 25, 64]. Comparing values from the outer bounds inwards allows us to place the largest squared values at the back: (-7)^2 = 49 and 8^2 = 64 (place 64), then (-7)^2 = 49 and 5^2 = 25 (place 49), and so on. Sorting these yields [0, 4, 9, 25, 49, 64].
Input
nums = [-5, -4, -2, -1]
Output
[1, 4, 16, 25]
Explanation: Squaring each negative element yields [25, 16, 4, 1]. Reordering them in non-decreasing order results in [1, 4, 16, 25].
Input
nums = [1, 3, 6, 10]
Output
[1, 9, 36, 100]
Explanation: Since all initial values are non-negative, squaring each element preserves the relative non-decreasing order: [1^2, 3^2, 6^2, 10^2] = [1, 9, 36, 100].
Input
nums = [-6, 0, 6]
Output
[0, 36, 36]
Explanation: Squaring each element yields 36, 0, and 36. Sorting these squared values from smallest to largest gives [0, 36, 36].
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- nums is sorted in non-decreasing order.
Optimal Approach & Strategy
Initialize two pointers at opposite ends of the sorted array and a write pointer at the end of a new result array. Compare the absolute values or squares at both pointers, write the larger value to the result array, and decrement the write pointer along with the chosen boundary pointer until all elements are processed in $O(N)$ time.
Brute Force Approach
Iterate through the array, square every element in place or in a new list, and then call a standard sorting function on the result. This takes $O(N \log N)$ time due to the sorting step and ignores the fact that the original array was pre-sorted.
Code Solutions
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortedSquares = function(nums) {
const n = nums.length;
const result = new Array(n);
let left = 0, right = n - 1;
let pos = n - 1;
while (left <= right) {
const leftSq = nums[left] * nums[left];
const rightSq = nums[right] * nums[right];
if (leftSq > rightSq) {
result[pos] = leftSq;
left++;
} else {
result[pos] = rightSq;
right--;
}
pos--;
}
return result;
};
// Driver code
const nums = [-7, -3, 0, 2, 5, 8];
console.log(sortedSquares(nums));#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> result(n);
int left = 0, right = n - 1;
int pos = n - 1;
while (left <= right) {
int leftSq = nums[left] * nums[left];
int rightSq = nums[right] * nums[right];
if (leftSq > rightSq) {
result[pos] = leftSq;
left++;
} else {
result[pos] = rightSq;
right--;
}
pos--;
}
return result;
}
};
int main() {
vector<int> nums = {-7, -3, 0, 2, 5, 8};
Solution sol;
vector<int> result = sol.sortedSquares(nums);
for (int i = 0; i < result.size(); ++i) {
cout << result[i] << (i < result.size() - 1 ? " " : "");
}
cout << endl;
return 0;
}import java.util.*;
class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] result = new int[n];
int left = 0, right = n - 1;
int pos = n - 1;
while (left <= right) {
int leftSq = nums[left] * nums[left];
int rightSq = nums[right] * nums[right];
if (leftSq > rightSq) {
result[pos] = leftSq;
left++;
} else {
result[pos] = rightSq;
right--;
}
pos--;
}
return result;
}
}
public class Main {
public static void main(String[] args) {
int[] nums = {-7, -3, 0, 2, 5, 8};
Solution sol = new Solution();
int[] result = sol.sortedSquares(nums);
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + (i < result.length - 1 ? " " : ""));
}
System.out.println();
}
}from typing import List
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1
while left <= right:
left_sq = nums[left] * nums[left]
right_sq = nums[right] * nums[right]
if left_sq > right_sq:
result[pos] = left_sq
left += 1
else:
result[pos] = right_sq
right -= 1
pos -= 1
return result
# Driver code
if __name__ == "__main__":
nums = [-7, -3, 0, 2, 5, 8]
sol = Solution()
print(sol.sortedSquares(nums))/**
* @param {number[]} nums
* @return {number[]}
*/
var sortedSquares = function(nums) {
const n = nums.length;
const result = new Array(n);
let left = 0, right = n - 1;
let pos = n - 1;
while (left <= right) {
const leftSq = nums[left] * nums[left];
const rightSq = nums[right] * nums[right];
if (leftSq > rightSq) {
result[pos] = leftSq;
left++;
} else {
result[pos] = rightSq;
right--;
}
pos--;
}
return result;
};
// Driver code
const nums = [-7, -3, 0, 2, 5, 8];
console.log(sortedSquares(nums));Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.