Squares of a Sorted Array
Explanation & Solution
Description
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Examples
Explanation: After squaring, the array becomes [16, 1, 0, 9, 100]. After sorting, it becomes [0, 1, 9, 16, 100].
Explanation: After squaring, the array becomes [49, 9, 4, 9, 121]. After sorting, it becomes [4, 9, 9, 49, 121].
Explanation: The square of -1 is 1.
Constraints
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4numsis sorted in non-decreasing order.
Approach
Two Pointers pattern
1. Recognize the Structure of the Input
The array is already sorted in non-decreasing order. This means the largest squared values must come from either the far left (most negative) or the far right (most positive) end of the array.
2. Set Up Two Pointers
Place a left pointer at index 0 and a right pointer at the last index. Create a result array of the same length, and a position index i starting from the end of the result array.
3. Compare Absolute Values
At each step, compare Math.abs(nums[left]) with Math.abs(nums[right]). Whichever is larger, square it and place it at result[i], then move that pointer inward.
4. Fill the Result from Back to Front
Since we always pick the largest remaining square, placing it at the back of result and decrementing i ensures the result is filled in non-decreasing order.
5. Return the Result
Once left passes right, every element has been processed. Return the result array.
Key Insight
Because the input is sorted, the largest squares live at the extremes of the array. By using two pointers converging inward and filling the output from the back, we achieve an O(n) time solution with a single pass — no sorting required.
Visualization
Press ▶ or use ← → to step through