Leetcode-977. Squares of a Sorted Array

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]

The provided solution addresses the problem by first squaring each element of the input array and then sorting the resulting array. It starts by iterating over the array using a loop and squaring each element of the array. After squaring all the elements, the array may not be in any particular order, so the next step is to sort the array in non-decreasing order. This is done using the `sort()` function from the C++ Standard Library. Once the array is sorted, the sorted array is returned as the final result.

For example, if the input array is `[-4, -1, 0, 3, 10]`, the first step will square each element, resulting in the array `[16, 1, 0, 9, 100]`. Then, the array is sorted to become `[0, 1, 9, 16, 100]`, which is the desired output. Similarly, for the input `[-7, -3, 2, 3, 11]`, after squaring the elements, we get `[49, 9, 4, 9, 121]`, and after sorting, the array becomes `[4, 9, 9, 49, 121]`, which is returned as the output.

The time complexity of this solution is O(n log n), which is dominated by the sorting step. While the squaring operation runs in O(n), the sorting operation takes O(n log n) time. The space complexity is O(1) assuming the sorting is done in-place, meaning that the solution does not require additional space apart from the input and output arrays. Overall, this approach is efficient and directly addresses the problem of returning the squares of the elements in a sorted order.

CODE:

class Solution {

public:

    vector<int> sortedSquares(vector<int>& nums) {

        int i,n;

        n=nums.size();

        for(i=0;i<n;i++){

        nums[i]=nums[i]*nums[i];

        }

        sort(nums.begin(),nums.end());

        return nums;

    }

}