31. Squares of a Sorted Array
🔗 LeetCode Problem: 977. Squares of a Sorted Array
📊 Difficulty: Easy
🏷️ Topics: Array, Two Pointers, Sorting
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:
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]
Constraints:
- 1 <= nums.length <= 10^4
- -10^4 <= nums[i] <= 10^4
- nums is sorted in non-decreasing order.
Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?
🎨 Visual Understanding
The Problem Visualized
Input: nums = [-4, -1, 0, 3, 10]
After squaring each element:
[-4, -1, 0, 3, 10]
↓ ↓ ↓ ↓ ↓
[16, 1, 0, 9, 100]
After sorting:
[0, 1, 9, 16, 100]
The Challenge: Why Sorting is Needed?
Original (sorted): [-4, -1, 0, 3, 10]
After squaring: [16, 1, 0, 9, 100] ← NOT sorted!
Why? Negative numbers become large when squared:
-4 squared = 16 (larger than -1 squared = 1)
The largest squares can be at EITHER end:
- Left end: Large negative numbers
- Right end: Large positive numbers
Example:
[-10, -5, 0, 5, 10]
↓ ↓ ↓ ↓ ↓
[100, 25, 0, 25, 100]
Largest values at BOTH ends!
Key Observation
For sorted array with negative and positive numbers:
Negative side: [-10, -5, -2]
Squares: [100, 25, 4] ← Decreasing order
Positive side: [2, 5, 10]
Squares: [4, 25, 100] ← Increasing order
Strategy: Use two pointers at both ends
Compare and pick the larger square each time
🎯 Approach 1: Square and Sort
The Most Natural Thinking 💭
Core Logic:
The straightforward approach:
1. Square each element in the array
2. Sort the squared array
3. Return the result
Why This Works: - Simple and easy to implement - Guaranteed to give correct result - Uses built-in sort
Why This Fails Requirements: - Time complexity O(n log n) due to sorting - Doesn't utilize the fact that input is sorted - Follow-up asks for O(n) solution
Implementation
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] result = new int[n];
// Square each element
for (int i = 0; i < n; i++) {
result[i] = nums[i] * nums[i];
}
// Sort the array
Arrays.sort(result);
return result;
}
⏰ Time: O(n log n) - O(n) for squaring + O(n log n) for sorting
💾 Space: O(n) - for result array (or O(log n) for sorting if in-place)
✅ Approach 2: Two Pointers (Optimal)
The Breakthrough Insight 💡
Core Logic:
Since input is sorted, largest squares are at the ends:
Use two pointers from both ends:
1. Left pointer at start (most negative)
2. Right pointer at end (most positive)
3. Compare squares: nums[left]² vs nums[right]²
4. Place larger square at end of result array
5. Move pointer with larger square
6. Fill result array from right to left
Key insight: Largest square always at either left or right end
Visual Explanation:
nums = [-4, -1, 0, 3, 10]
L R
result = [_, _, _, _, _]
↑ fill from right
Step 1: Compare |-4|² vs |10|²
16 vs 100
100 is larger → result[4] = 100, R--
Step 2: Compare |-4|² vs |3|²
16 vs 9
16 is larger → result[3] = 16, L++
Step 3: Compare |-1|² vs |3|²
1 vs 9
9 is larger → result[2] = 9, R--
Step 4: Compare |-1|² vs |0|²
1 vs 0
1 is larger → result[1] = 1, L++
Step 5: Only 0 left
result[0] = 0
Final: [0, 1, 9, 16, 100]
Why Fill from Right to Left:
We pick the LARGER square each time
Larger squares should go at the END of result array
So we fill result from right to left
Alternative: Pick smaller square and fill left to right
But comparing larger is more intuitive
Implementation
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] result = new int[n];
int left = 0;
int right = n - 1;
int pos = n - 1; // Fill result from right to left
while (left <= right) {
int leftSquare = nums[left] * nums[left];
int rightSquare = nums[right] * nums[right];
if (leftSquare > rightSquare) {
// Left square is larger, place it at current position
result[pos] = leftSquare;
left++;
} else {
// Right square is larger or equal, place it at current position
result[pos] = rightSquare;
right--;
}
pos--; // Move to next position (going left)
}
return result;
}
⏰ Time: O(n) - single pass through array
💾 Space: O(n) - for result array (O(1) excluding output)
🔍 Step-by-Step Execution
Example: nums = [-4, -1, 0, 3, 10]
Initial State:
═══════════════════════════════════════════════════════════════════
nums = [-4, -1, 0, 3, 10]
L R
result = [_, _, _, _, _]
pos=4
Step 1: Compare left and right squares
═══════════════════════════════════════════════════════════════════
leftSquare = (-4)² = 16
rightSquare = (10)² = 100
Compare: 16 vs 100
100 > 16 → Choose right
result[4] = 100
right = 3, pos = 3
nums = [-4, -1, 0, 3, 10]
L R
result = [_, _, _, _, 100]
pos=3
Step 2: Compare left and right squares
═══════════════════════════════════════════════════════════════════
leftSquare = (-4)² = 16
rightSquare = (3)² = 9
Compare: 16 vs 9
16 > 9 → Choose left
result[3] = 16
left = 1, pos = 2
nums = [-4, -1, 0, 3, 10]
L R
result = [_, _, _, 16, 100]
pos=2
Step 3: Compare left and right squares
═══════════════════════════════════════════════════════════════════
leftSquare = (-1)² = 1
rightSquare = (3)² = 9
Compare: 1 vs 9
9 > 1 → Choose right
result[2] = 9
right = 2, pos = 1
nums = [-4, -1, 0, 3, 10]
L R
result = [_, _, 9, 16, 100]
pos=1
Step 4: Compare left and right squares
═══════════════════════════════════════════════════════════════════
leftSquare = (-1)² = 1
rightSquare = (0)² = 0
Compare: 1 vs 0
1 > 0 → Choose left
result[1] = 1
left = 2, pos = 0
nums = [-4, -1, 0, 3, 10]
L=R
result = [_, 1, 9, 16, 100]
pos=0
Step 5: Last element (left == right)
═══════════════════════════════════════════════════════════════════
leftSquare = (0)² = 0
rightSquare = (0)² = 0
result[0] = 0
left = 3, pos = -1
Loop ends (left > right)
═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: [0, 1, 9, 16, 100]
═══════════════════════════════════════════════════════════════════
Another Example: nums = [-7, -3, 2, 3, 11]
Initial: left=0, right=4, pos=4
Step 1: (-7)²=49 vs (11)²=121 → 121 > 49
result[4] = 121, right=3
result = [_, _, _, _, 121]
Step 2: (-7)²=49 vs (3)²=9 → 49 > 9
result[3] = 49, left=1
result = [_, _, _, 49, 121]
Step 3: (-3)²=9 vs (3)²=9 → 9 == 9 (choose right)
result[2] = 9, right=2
result = [_, _, 9, 49, 121]
Step 4: (-3)²=9 vs (2)²=4 → 9 > 4
result[1] = 9, left=2
result = [_, 9, 9, 49, 121]
Step 5: left==right, (2)²=4
result[0] = 4
result = [4, 9, 9, 49, 121]
🔍 Edge Cases
Case 1: All positive numbers
Input: nums = [1, 2, 3, 4, 5]
Output: [1, 4, 9, 16, 25]
Explanation: Already sorted after squaring
Case 2: All negative numbers
Input: nums = [-5, -4, -3, -2, -1]
Output: [1, 4, 9, 16, 25]
Explanation: Reversed order after squaring
Case 3: Single element
Input: nums = [5]
Output: [25]
Case 4: Two elements (both negative)
Input: nums = [-3, -1]
Output: [1, 9]
Case 5: Two elements (one negative, one positive)
Input: nums = [-1, 2]
Output: [1, 4]
Case 6: Contains zero
Input: nums = [-2, 0, 2]
Output: [0, 4, 4]
Case 7: All zeros
Input: nums = [0, 0, 0]
Output: [0, 0, 0]
Case 8: Large range
Input: nums = [-10000, 0, 10000]
Output: [0, 100000000, 100000000]
Common Mistakes
Mistake 1: Not utilizing sorted input property
❌ Wrong:
// Just square and sort, ignoring that input is sorted
Arrays.sort(result);
✓ Right:
// Use two pointers to leverage sorted property
Reason: Follow-up asks for O(n) solution
Mistake 2: Filling result array from left to right
❌ Wrong:
int pos = 0;
while (left <= right) {
if (leftSquare > rightSquare) {
result[pos] = leftSquare; // Wrong direction
}
pos++;
}
✓ Right:
int pos = n - 1;
// ... pick larger square
pos--;
Reason: We pick LARGER squares, which should go at the END
Mistake 3: Using absolute value incorrectly
❌ Wrong:
if (Math.abs(nums[left]) > Math.abs(nums[right])) {
result[pos] = nums[left]; // Not squared!
}
✓ Right:
int leftSquare = nums[left] * nums[left];
int rightSquare = nums[right] * nums[right];
if (leftSquare > rightSquare) {
result[pos] = leftSquare;
}
Reason: Need to store the SQUARE, not the original value
Mistake 4: Wrong loop condition
❌ Wrong:
while (left < right) { // Missing equal case
...
}
✓ Right:
while (left <= right) {
...
}
Reason: Need to process the element when left == right
Mistake 5: Not moving pointers correctly
❌ Wrong:
if (leftSquare > rightSquare) {
result[pos] = leftSquare;
right--; // Wrong pointer!
}
✓ Right:
if (leftSquare > rightSquare) {
result[pos] = leftSquare;
left++; // Move the pointer we used
}
Reason: Move the pointer corresponding to the square we picked
Mistake 6: Comparing values instead of squares
❌ Wrong:
if (nums[left] > nums[right]) {
result[pos] = nums[left] * nums[left];
}
✓ Right:
int leftSquare = nums[left] * nums[left];
int rightSquare = nums[right] * nums[right];
if (leftSquare > rightSquare) {
result[pos] = leftSquare;
}
Reason: -10 < 5, but (-10)² > 5²
🎯 Key Takeaways
⚡ Algorithm Comparison
Approach 1: Square and Sort
Time: O(n log n)
Space: O(n) or O(log n)
Use: Simple but not optimal
Approach 2: Two Pointers (RECOMMENDED)
Time: O(n)
Space: O(n) for output (O(1) excluding output)
Use: Optimal solution, meets follow-up requirement
🔑 The Core Insight
Key Observation: For sorted array, largest squares are at the ENDS
Why?
- Negative numbers: More negative → Larger square
Example: -10² = 100 > -5² = 25
- Positive numbers: More positive → Larger square
Example: 10² = 100 > 5² = 25
Strategy:
1. Use two pointers at both ends
2. Compare squares at both ends
3. Pick the LARGER square
4. Fill result array from RIGHT to LEFT
5. Move the pointer of the square we picked
Direction Matters:
- Pick LARGER → Fill from right (large values at end)
- Pick SMALLER → Fill from left (small values at start)
Formula:
leftSquare = nums[left] * nums[left]
rightSquare = nums[right] * nums[right]
Pick max(leftSquare, rightSquare)
🎯 Pattern Recognition
Problem Type: Sorted Array Processing
Core Pattern: Two Pointers from Both Ends
When to Apply:
✓ Array is sorted
✓ Need to process from both ends
✓ Extreme values (min/max) are at ends
✓ Can build result by comparing ends
Key Techniques:
→ Two pointers at opposite ends
→ Compare values at both pointers
→ Make decision based on comparison
→ Move pointer based on choice
→ Fill result in appropriate direction
Related Problems:
- Container With Most Water (LC 11)
- Trapping Rain Water (LC 42)
- 3Sum (LC 15)
- Two Sum II (LC 167)
🧠 Interview Strategy
Step 1: "Array is sorted, need to square and sort"
Step 2: "Naive: square all, then sort - O(n log n)"
Step 3: "Better: largest squares at ends"
Step 4: "Two pointers from both ends"
Step 5: "Compare, pick larger, fill from right"
Step 6: "O(n) time, O(1) extra space"
Key Points to Mention:
- Input is sorted (important property)
- Largest squares at either end
- Two pointers approach for O(n)
- Fill result from right to left
- Compare squared values, not original values
📝 Quick Revision Notes
🎯 Core Concept:
For sorted array, largest squares are at the ENDS. Use two pointers from both ends, compare squares, pick larger, fill result right to left.
⚡ Quick Implementation:
public int[] sortedSquares(int[] a) {
int len = a.length;
int[] res = new int[len];
int index = 0;
// 2 pointers (pointers start in between instead of
// regular start or end)
// find index of zero or first positive number
// basically that divides -ve numbers and 0/+ve numbers
int i = 0;
while (i < len) {
if(a[i] >= 0) {
break;
}
i++;
}
int j = i - 1;
// Loop when both i and j exists.
while (i < len && j >= 0) {
if(Math.abs(a[i]) < Math.abs(a[j])) {
res[index] = a[i] * a[i];
i++;
} else {
res[index] = a[j] * a[j];
j--;
}
index++;
}
// Loop for remaining i if exists
while (i < len) {
res[index] = a[i] * a[i];
i++;
index++;
}
// Loop for remaining j if exists
while (j >= 0) {
res[index] = a[j] * a[j];
j--;
index++;
}
return res;
}
🔑 Key Insights:
- Sorted property: Largest squares at ENDS (negative or positive extremes)
- Two pointers: Start from both ends (left=0, right=n-1)
- Compare squares:
leftSquarevsrightSquare(not original values) - Pick larger: Larger square goes to result
- Fill right to left:
pos = n-1, decrement after each placement - Move pointer: Move the pointer of the square we picked
- Loop condition:
left <= right(process when equal too) - Time: O(n), Space: O(n) for result (O(1) excluding output)
- Why not abs(): Squaring is needed anyway, no benefit
🎪 Memory Aid:
"Ends have LARGEST squares, pick and place RIGHT to LEFT!"
Think: "Sorted input → Two pointers → Fill backwards"
Related Patterns
- Two Sum II - Input Array Is Sorted (LC 167)
- Container With Most Water (LC 11)
- 3Sum (LC 15)
- Trapping Rain Water (LC 42)
Happy practicing! 🎯