Square a Sorted Array and Return the Squares in Order

### Problem Given `nums` in nondecreasing order, return every value squared, also in nondecreasing order. Negative values may cause squared values to appear in a different order. ```cpp class Solution { public: vector<int> sortedSquares(vector<int>& nums); }; ``` ### Examples **Example 1:** ```text Input: nums = [-5,-2,1,4] Output: [1,4,16,25] Explanation: The squared values25,4,1,16 are rearranged into increasing order. ``` **Example 2:** ```text Input: nums = [-3,-1] Output: [1,9] Explanation: Among negative inputs, the smaller original value has the larger square. ``` ### Constraints - The number of elements is at least1 and at most10000. - Every input value is an integer between-10000 and10000, inclusive. - The given array is already ordered from smallest to largest, with ties allowed. ### Contract considerations Nondecreasing order permits duplicates, and every duplicate square remains in the output. ```hint Read the boundary condition The largest remaining square is at one of the two ends of the sorted input interval. ``` ### Boundary reminders Nondecreasing order permits duplicates, and every duplicate square remains in the output. ### Optional extensions Original follow-up: obtain O(n) time without squaring and sorting with a comparison sort. The two-end method does so.