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] <= 104nums 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?This approach involves first squaring every element, and then sorting the resultant array. Since the sorting algorithm typically used is O(n log n) in terms of time complexity, this approach is straightforward but not the most optimal for this problem.
In this solution, we first compute the square of each element in the array. Thereafter, we use the qsort function from the standard library to sort the squared elements. This approach directly modifies the input array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as sorting is done in place.
Utilizing a two-pointer technique allows us to traverse the array from both ends, taking advantage of the non-decreasing order of the input array. By comparing the squares of elements from both ends, we can construct the output array from the largest to the smallest square, ensuring an O(n) time complexity.
In this solution, two pointers start at the ends of the array. The larger square from the two ends is added to the result array from the last position to the first, effectively sorting as we fill the array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) as we traverse the array only once.
Space Complexity: O(n) due to the result array.
| Approach | Complexity |
|---|---|
| Approach 1: Sorting After Squaring | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Two Pointer Technique | Time Complexity: O(n) as we traverse the array only once. |
ANGRY Software Developer vs Sleepy O(n) Engineer on Squares of a Sorted Array, Leetcode 977 • Greg Hogg • 401,202 views views
Watch 9 more video solutions →Practice Squares of a Sorted Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor