Squares of a Sorted Array
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
nums = [-7,-3,2,3,11][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
Recognizing that the largest squares come from the array's ends, a two-pointer approach can be used. By comparing the squares at the left and right pointers, the algorithm places the larger square at the current position from the end of the output array and moves the corresponding pointer inward. This process continues until the pointers cross, resulting in a sorted squares array in O(n) time.
Optimal Approach
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.
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
| 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 |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public int[] sortedSquares(int[] nums) { |
| 5 | int n = nums.length; |
| 6 | int[] ans = new int[n]; |
| 7 | |
| 8 | int l = 0, r = n - 1; |
| 9 | int i = n - 1; |
| 10 | |
| 11 | while (l <= r) { |
| 12 | int left_sq = nums[l] * nums[l]; |
| 13 | int right_sq = nums[r] * nums[r]; |
| 14 | |
| 15 | if (left_sq > right_sq) { |
| 16 | ans[i] = left_sq; |
| 17 | l++; |
| 18 | } else { |
| 19 | ans[i] = right_sq; |
| 20 | r--; |
| 21 | } |
| 22 | |
| 23 | i--; |
| 24 | } |
| 25 | |
| 26 | return ans; |
| 27 | } |
| 28 | } |
| 1 | #include <vector> |
| 2 | using namespace std; |
| 3 | |
| 4 | class Solution { |
| 5 | public: |
| 6 | vector<int> sortedSquares(vector<int>& nums) { |
| 7 | int n = nums.size(); |
| 8 | vector<int> ans(n, 0); |
| 9 | |
| 10 | int l = 0, r = n - 1; |
| 11 | int i = n - 1; |
| 12 | |
| 13 | while (l <= r) { |
| 14 | int left_sq = nums[l] * nums[l]; |
| 15 | int right_sq = nums[r] * nums[r]; |
| 16 | |
| 17 | if (left_sq > right_sq) { |
| 18 | ans[i] = left_sq; |
| 19 | l++; |
| 20 | } else { |
| 21 | ans[i] = right_sq; |
| 22 | r--; |
| 23 | } |
| 24 | |
| 25 | i--; |
| 26 | } |
| 27 | |
| 28 | return ans; |
| 29 | } |
| 30 | }; |
| 1 | var sortedSquares = function(nums) { |
| 2 | const n = nums.length; |
| 3 | const ans = new Array(n).fill(0); |
| 4 | |
| 5 | let l = 0, r = n - 1; |
| 6 | let i = n - 1; |
| 7 | |
| 8 | while (l <= r) { |
| 9 | const left_sq = nums[l] * nums[l]; |
| 10 | const right_sq = nums[r] * nums[r]; |
| 11 | |
| 12 | if (left_sq > right_sq) { |
| 13 | ans[i] = left_sq; |
| 14 | l++; |
| 15 | } else { |
| 16 | ans[i] = right_sq; |
| 17 | r--; |
| 18 | } |
| 19 | |
| 20 | i--; |
| 21 | } |
| 22 | |
| 23 | return ans; |
| 24 | }; |
Step-by-Step Solution
Initialize Pointers and Output Array
| 3 | n = len(nums)
|
| 4 | ans = [0] * n
|
| 6 | l, r = 0, n - 1
|
| 7 | i = 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
| 9 | while l <= r:
|
| 10 | left_sq = nums[l] * nums[l]
|
| 11 | right_sq = nums[r] * nums[r]
|
| 13 | if left_sq > right_sq:
|
| 14 | ans[i] = left_sq
|
| 15 | l += 1
|
| 16 | else:
|
| 17 | ans[i] = right_sq
|
| 18 | r -= 1
|
| 20 | i -= 1
|
Objective
To iteratively compare squares at the left and right pointers, place the larger square at the current output index, and move pointers inward accordingly.
Key Insight
By always placing the larger square at the current output position from the end, the algorithm ensures the output array is sorted without additional sorting. Moving pointers inward discards the processed element, shrinking the search space until all elements are placed.
Interview Quick-Check
Core Logic
At each iteration, compare squares at left and right pointers, place the larger at output[i], then move the pointer corresponding to the larger square inward and decrement i.
State & Boundaries
The loop continues while left pointer is less than or equal to right pointer, ensuring all elements are processed.
Common Pitfalls & Bugs
Incorrect pointer movement or failing to decrement the output index can cause incorrect results or infinite loops.
Return the Sorted Squares Array
| 22 | return ans |
Objective
To return the fully populated output array containing the squares in sorted order.
Key Insight
After the loop completes, the output array is guaranteed to be sorted because the largest squares were placed first, moving backward to the smallest.
Interview Quick-Check
Core Logic
Returning the output array completes the function, providing the sorted squares as required.
Line Analysis
This solution has 1 Critical line interviewers watch for.
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.
ans[i] = left_sqAssign the larger left square to the current output index i.
Placing the larger square at the end of the output array maintains sorted order without additional sorting.
ans[i] = right_sqAssign the larger right square to the current output index i.
Placing the larger right square at the output index maintains the sorted order of the output array.
i -= 1Decrement the output index i to fill the output array from end to start.
Decreasing i ensures the next largest square is placed in the correct position, maintaining sorted order.
ans = [0] * nInitialize the output array ans with zeros of length n.
Preallocating the output array allows direct assignment by index, enabling O(1) writes and avoiding dynamic resizing overhead.
i = n - 1Initialize i to the last index of ans, where the next largest square will be written.
The index i starts at the last position of the output array so that each step can place the current largest square and then move left, building the sorted result from largest to smallest.
l += 1Increment the left pointer to move inward after placing its square.
Moving the left pointer inward discards the processed element, shrinking the search space.
else:Else branch for when the right square is greater or equal.
Handles the case where the right square is larger or equal, ensuring correct placement in the output array.
r -= 1Decrement the right pointer to move inward after placing its square.
Moving the right pointer inward discards the processed element, shrinking the search space.
while l <= r:Begin a loop that continues while the left pointer is less than or equal to the right pointer.
This loop condition ensures all elements between the pointers are processed exactly once, covering the entire array.
left_sq = nums[l] * nums[l]Calculate the square of the element at the left pointer.
Squaring the left element prepares it for comparison to determine which square is larger.
right_sq = nums[r] * nums[r]Calculate the square of the element at the right pointer.
Squaring the right element prepares it for comparison to determine which square is larger.
l, r = 0, n - 1Initialize l and r to the leftmost and rightmost indices of nums.
The two pointers l and r start at the opposite ends of the array so we can always compare the elements with the largest absolute values, which are the only candidates for the next largest square.
return ansReturn the output array containing sorted squares.
Returning the fully populated output array completes the function, providing the required sorted squares.
n = len(nums)Store the length of the input array nums.
Caching the length avoids repeated calls to len(nums) and clarifies the array size for subsequent operations.
Test Your Understanding
Why does the two-pointer approach fill the output array from the end rather than from the start?
Because the largest squares come from the ends of the input array, placing them at the end of the output array ensures the array is filled in non-decreasing order without needing extra sorting.
Related Problems
Two Pointers pattern
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