Sort array after converting elements to their squares | GFG Solution

Given an array A consisting of both positive and negative integers of size N which are sorted. Your task is to sort the square of the numbers of the array.

 

Example 1:

Input:
N = 6
A[] = {-6, -3, -1, 2, 4, 5}
Output: 1 4 9 16 25 36
Explanation: 
Square of the given array is -
[36, 9, 1, 4,16, 25]. When this array 
is sorted, it gives - [1, 4, 9, 16, 25, 36]

 

Example 2:

Input:
N = 5
A[]  = {-5, -4, -2, 0, 1}
Output: 0 1 4 16 25

Your Task:  
You don't need to read input or print anything. Your task is to complete the function sortSquares() which takes the array A[] and its size N as inputs and returns an array of size N.

 

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

 

Constraints:
1 <= N <= 2 * 104
-104 <= Ai <= 104

class Solution

{

   public:

    vector<int> sortSquares(int v[], int n)

    {

        vector<int>ans(n,0);

        int st=0,end=n-1;

        int i=n-1;

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

            if(v[i]>=0)break;

        }

        int j=n-1;

        while(st<i && j>=i){

            if(v[st]*v[st]>=v[j]*v[j]){

                ans[end]=v[st]*v[st];

                st++;

                end--;

            }

            else{

                ans[end]=v[j]*v[j];

                j--;

                end--;

            }

        }

        if(j!=i-1){

            while(j>=i){

                ans[end]=v[j]*v[j];

                j--;

                end--;

            }

        }

        while(st<i){

            ans[end]=v[st]*v[st];

            st++;

            end--;

        }

        return ans;

    }

};