Sorted Squares — Problem Statement & Solution Guide
Problem Description
Given a sorted array of integers, compute the square of each element and return the resulting array in sorted order.
Examples
Input
[-4, -1, 0, 3, 10]
Output
[0, 1, 9, 16, 100]
Explanation: Step-by-step: with input [-4, -1, 0, 3, 10], we square each element to get [16, 1, 0, 9, 100], then sort the array in ascending order, giving output [0, 1, 9, 16, 100]
Input
[2, 3, 5, 7, 11]
Output
[4, 9, 25, 49, 121]
Explanation: Step-by-step: with input [2, 3, 5, 7, 11], we square each element to get [4, 9, 25, 49, 121], then sort the array in ascending order, giving output [4, 9, 25, 49, 121]
Constraints
- 1 <= n <= 10^4
- -10^4 <= arr[i] <= 10^4
Optimal Approach & Strategy
Two pointers at start and end. Compare absolute values, square the larger one, and place it at the end of a new result array. Move pointer inwards. Time O(N), Space O(N).
Brute Force Approach
Square all elements and then sort. Time O(N log N).
Verified Code Solutions
function solution(nums) { return nums.map(x => x * x).sort((a, b) => a - b); }class Solution { public: vector<int> solution(vector<int>& nums) { vector<int> squared; for (int num : nums) { squared.push_back(num * num); } sort(squared.begin(), squared.end()); return squared; } };import java.util.Arrays; class Solution { public int[] solution(int[] nums) { int[] squared = new int[nums.length]; for (int i = 0; i < nums.length; i++) { squared[i] = nums[i] * nums[i]; } Arrays.sort(squared); return squared; } }def solution(nums): return sorted([x ** 2 for x in nums])function solution(nums) { return nums.map(x => x * x).sort((a, b) => a - b); }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.