Squares of a Sorted Array
EasyPrompt
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 <= 104-104 <= nums[i] <= 104numsis 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?Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to first square every element in the input array and then sort the resulting array. This is simple to implement but not the most efficient.
Algorithm
- Create a new array
resultof the same size asnums. - Iterate through
numswith an indexifrom 0 ton-1. - For each element
nums[i], calculate its square:squared = nums[i] * nums[i]. - Store the result in the new array:
result[i] = squared. - After the loop, sort the
resultarray using a standard sorting function. - Return the sorted
resultarray.
import java.util.Arrays; class Solution { public int[] sortedSquares(int[] nums) { int n = nums.length; int[] result = new int[n]; for (int i = 0; i < n; i++) { result[i] = nums[i] * nums[i]; } Arrays.sort(result); return result; }}Walkthrough
This method involves two main steps. First, we iterate through the input array nums from beginning to end. For each number, we calculate its square and store it in a new array, let's call it result. After this first pass, the result array will contain the squares of all elements from nums, but it will not be sorted. For example, if nums is [-4, -1, 0, 3, 10], the result array will be [16, 1, 0, 9, 100]. The second step is to sort this result array in non-decreasing order. Standard sorting algorithms like Merge Sort or Quick Sort can be used, which typically have a time complexity of O(n log n). After sorting, result becomes [0, 1, 9, 16, 100], which is the final answer.
Complexity
Time
O(n log n), where n is the number of elements in the array. Squaring each element takes O(n) time, and sorting the resulting array takes O(n log n) time. The sorting step dominates the complexity.
Space
O(n) or O(log n). We need O(n) space for the new array to store the squares. The space complexity of `Arrays.sort()` in Java for primitives is O(log n) due to its dual-pivot quicksort implementation. Thus, the total space is dominated by the O(n) output array.
Trade-offs
Pros
Simple to understand and implement.
Cons
Not the most efficient solution as it doesn't utilize the fact that the input array is already sorted.
The O(n log n) time complexity can be improved upon.
Solutions
Solution
class Solution {public int[] sortedSquares(int[] nums) { int n = nums.length; int[] res = new int[n]; for (int i = 0, j = n - 1, k = n - 1; i <= j;) { if (nums[i] * nums[i] > nums[j] * nums[j]) { res[k--] = nums[i] * nums[i]; ++i; } else { res[k--] = nums[j] * nums[j]; --j; } } return res; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.