977. Squares of a Sorted Array
Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order. Example 1: Input: [-4,-1,0,3,10] Output: [0,1,9,16,100] Example 2: Input: [-7,-3,2,3,11] Output: [4,9,9,49,121] Note: 1 <= A.length <= 10000 -10000 <= A[i] <= 10000 A is sorted in non-decreasing order. --- Intuition Sorting the squared array is trivial - O(n log n) If array contains all positives, results is already sorted - no op If array contains at least one negative -- check the first element, then two pointers at two ends can be used to build the result array from the end -- Time - O(n) Space - O(n) - output array ---