Log inSign up
easyLeetCodeNot Started

Squares of a Sorted Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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

Example 1 · Standard Array with Negative and Positive Numbers:

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 · All Negative Numbers:

Input: nums = [-7, -3, 2, 3, 11]
Output: [4, 9, 9, 49, 121]
Explanation: Squared values: [49, 9, 4, 9, 121]. Sorted result: [4, 9, 9, 49, 121].

Example 3 · All Positive Numbers:

Input: nums = [1, 2, 3, 4, 5]
Output: [1, 4, 9, 16, 25]
Explanation: Since all numbers are positive, squaring preserves sorted order directly.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Properties of absolute values and squaring negative numbers
  • Two Pointers converging from opposite ends
  • Allocating and filling a result array backwards

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Recognize why the largest squared numbers are always located at the array endpoints.
  • Master the opposite-ends two-pointer pattern with backward result insertion.
  • Achieve linear O(N) time without calling sort library functions.
  • Write idiomatic, standalone implementations across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input is sorted but contains both negative and positive numbers.
  • Squaring makes large negative numbers large positive numbers.
  • The maximum values of the squared array are always at the boundaries (left and right extremes).

Algorithmic Decision Tree:

  • Whenever the maximum values reside at the two outer extremes of a sorted array: Use Two Pointers converging inward and fill the result array from back to front in O(N) time.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Square All Elements & Comparison Sort

Intuition

Square every number in the array, then apply standard comparison sort in O(N log N) time.

Algorithm

  1. 1. For each element x in nums: replace x with x * x.
  2. 2. Sort the squared array using standard library sort.
  3. 3. Return the sorted array in O(N log N) time.

Square All Elements & Comparison Sort

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [-4, -1, 0, 3, 10]
Current operationSTEP 1 OF 6
Phase 1 — Square Each Element: Iterate over nums and compute square: (-4)^2 = 16, (-1)^2 = 1, 0^2 = 0, 3^2 = 9, 10^2 = 100
Visual state
Values and pointers at this exact step
array
S
16
1
0
9
100
0
↑ Squared
1
2
3
4
Variables at this step
Squared Array
[16, 1, 0, 9, 100]
Check / comparison
Squared array = [16, 1, 0, 9, 100].
Decision / next transition
All elements squared.
Why this step matters

Phase 1 — Square Each Element: Iterate over nums and compute square: (-4)^2 = 16, (-1)^2 = 1, 02 = 0, 32 = 9, 102 = 100.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<int> sortedSquares(vector<int>& nums) {
17 for (int& x : nums) x = x * x;
18 sort(nums.begin(), nums.end());
19 return nums;
20 }
21};
22
23int main() {
24 Solution sol;
25 vector<int> nums = {-4, -1, 0, 3, 10};
26 vector<int> res = sol.sortedSquares(nums);
27
28 cout << "Sorted Squares: [";
29 for (size_t i = 0; i < res.size(); ++i) {
30 cout << res[i] << (i + 1 < res.size() ? ", " : "");
31 }
32 cout << "]" << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N log N) — Squaring takes O(N) and comparison sorting takes O(N log N).
  • Space complexity: O(1) — In-place sort takes O(1) auxiliary space.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Separate Positive and Negative Arrays + 2-Way Merge

Intuition

Separate negative numbers (squared and reversed) and non-negative numbers, then merge two sorted arrays.

Algorithm

  1. 1. Find pivot index where elements become >= 0.
  2. 2. Collect and reverse squares of negative elements into list A.
  3. 3. Collect squares of non-negative elements into list B.
  4. 4. Merge sorted lists A and B in linear O(N) time.
  5. 5. Return merged array.

Separate Positive & Negative Arrays + 2-Way Merge

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 1, 9, 16, 100]
Current operationSTEP 1 OF 6
Phase 1 — Partition into Negative & Positive Parts: Negatives: [-4, -1]
Visual state
Values and pointers at this exact step
array
S
—
—
—
—
—
0
↑ Split
1
2
3
4
Variables at this step
Negatives
[-4, -1]
Positives
[0, 3, 10]
Check / comparison
Split at non-negative boundary index 2.
Decision / next transition
Negatives = [-4, -1], Positives = [0, 3, 10].
Why this step matters

Phase 1 — Partition into Negative & Positive Parts: Negatives: [-4, -1]. Non-negatives: [0, 3, 10].

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<int> sortedSquares(vector<int>& nums) {
17 vector<int> neg, pos;
18 for (int x : nums) {
19 if (x < 0) neg.push_back(x * x);
20 else pos.push_back(x * x);
21 }
22 reverse(neg.begin(), neg.end());
23
24 vector<int> res;
25 int i = 0, j = 0;
26 while (i < neg.size() && j < pos.size()) {
27 if (neg[i] < pos[j]) res.push_back(neg[i++]);
28 else res.push_back(pos[j++]);
29 }
30 while (i < neg.size()) res.push_back(neg[i++]);
31 while (j < pos.size()) res.push_back(pos[j++]);
32 return res;
33 }
34};
35
36int main() {
37 Solution sol;
38 vector<int> nums = {-4, -1, 0, 3, 10};
39 vector<int> res = sol.sortedSquares(nums);
40
41 cout << "Sorted Squares: [";
42 for (size_t i = 0; i < res.size(); ++i) {
43 cout << res[i] << (i + 1 < res.size() ? ", " : "");
44 }
45 cout << "]" << endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(N) — Separation takes O(N) and 2-way merge takes O(N). Total time is O(N).
  • Space complexity: O(N) — Requires auxiliary arrays to store split partitions, taking O(N) space.

3. Two Pointers Filling Back-to-Front (Optimal & Standard)

Intuition

Use two pointers at the ends (left = 0, right = n - 1) and place the larger square at the back of the result array.

Algorithm

  1. 1. Initialize left = 0, right = n - 1, pos = n - 1, and result array of size n.
  2. 2. While left <= right: - leftSq = nums[left] * nums[left] - rightSq = nums[right] * nums[right] - If leftSq > rightSq: result[pos] = leftSq, left++ - Else: result[pos] = rightSq, right-- - pos--.
  3. 3. Return result.

Two Pointers Filling Back-to-Front (O(N) Time & O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [-4, -1, 0, 3, 10]
Current operationSTEP 1 OF 6
Phase 1 — Invariant Setup: The largest squared values MUST be at either the far left (most negative) or far right (most positive)
Visual state
Values and pointers at this exact step
array
S
-4
-1
0
3
10
0
↑ L=0 (16)
1
2
3
4
↑ R=4 (100)
Variables at this step
L
0
R
4
L^2
16
R^2
100
Winner
R (100)
pos
4
res
[—, —, —, —, 100]
Check / comparison
L = 0 (val -4, sq 16), R = 4 (val 10, sq 100).
Decision / next transition
100 > 16: Place 100 at res[4]. Decrement R to 3, decrement pos to 3.
Why this step matters

Phase 1 — Invariant Setup: The largest squared values MUST be at either the far left (most negative) or far right (most positive). L = 0, R = 4, pos = 4 (fill from back).

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<int> sortedSquares(vector<int>& nums) {
17 int n = nums.size();
18 vector<int> res(n);
19 int left = 0, right = n - 1, pos = n - 1;
20
21 while (left <= right) {
22 int lSq = nums[left] * nums[left];
23 int rSq = nums[right] * nums[right];
24 if (lSq > rSq) {
25 res[pos--] = lSq;
26 left++;
27 } else {
28 res[pos--] = rSq;
29 right--;
30 }
31 }
32 return res;
33 }
34};
35
36int main() {
37 Solution sol;
38 vector<int> nums = {-4, -1, 0, 3, 10};
39 vector<int> res = sol.sortedSquares(nums);
40
41 cout << "Sorted Squares: [";
42 for (size_t i = 0; i < res.size(); ++i) {
43 cout << res[i] << (i + 1 < res.size() ? ", " : "");
44 }
45 cout << "]" << endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(N) — In each step one element is placed into result; loop runs exactly N times in O(N) time.
  • Space complexity: O(1) — Result array does not count toward auxiliary space. Extra space is O(1).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Square All Elements & Comparison SortO(N log N)O(1)Square every number in the array, then apply standard comparison sort in O(N log N) time.Repeated redundant scans over the input.
2.Approach 2: Separate Positive and Negative Arrays + 2-Way MergeO(N)O(N)Separate negative numbers (squared and reversed) and non-negative numbers, then merge two sorted arrays.Auxiliary memory allocation or sorting step.
3.Approach 3: Two Pointers Filling Back-to-Front (Optimal & Standard)OptimalO(N)O(1)Use two pointers at the ends (left = 0, right = n - 1) and place the larger square at the back of the result array.None. Asymptotically optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • All Negative Numbers — Input: nums = [-5, -3, -2, -1], Expected: [1, 4, 9, 25] — Squaring reverses the order of purely negative sorted numbers.
  • All Positive Numbers — Input: nums = [1, 2, 3, 4], Expected: [1, 4, 9, 16] — Right pointer will decrement on every step until left == right.
  • Single Element Array — Input: nums = [-3], Expected: [9] — Loop runs once and returns [9].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Squares of a Sorted Array?

2.Why is the brute force approach suboptimal for large inputs in Squares of a Sorted Array?

3.Which data structure or technique enables the optimal solution for Squares of a Sorted Array?

Back to DSA Sheet