Last Updated: 10 Mar, 2021
Squares of a Sorted Array
Easy
Asked in companies
You are given an array/list ‘ARR’ of ‘N’ integers. You have to generate an array/list containing squares of each number in ‘ARR’, sorted in increasing order.
For example :
Input:
‘ARR’ = [-6,-3, 2, 1, 5]
If we take a square of each element then the array/list will become [36, 9, 4, 1, 25].
Then the sorted array/list will be [1, 4, 9, 25, 36].
Output :
[1, 4, 9, 25, 36].
Input Format:
The first line of input contains a single integer ‘T’, representing the number of test cases.
Then the ‘T’ test cases follow.
The first line of each test case contains a single integer ‘N’ denoting the size of ‘ARR’.
The second line contains ‘N’ space-separated distinct integers denoting the array elements.
Output format:
For each test case, print the array elements separated by a single space.
The output of every test case will be printed in a separate line.
Note :
You don’t have to print anything, it has already been taken care of. Just implement the given function.
Constraints
1 <= T <=100
1 <= N <= 10^4
-10^4 <= ‘ARR[i]’ <= 10^4
Where 'ARR[i]' denotes the value of 'ARR' at index 'i'.
Time limit: 1 sec
Approaches
Approach: The idea is very simple. In the first step, we will traverse the whole array/list ‘ARR’ and replace each element with its square. Then in the second step sort ‘ARR’ and return it.
Algorithm:
- Iterate over ‘ARR’ for 0 <= i < ‘N’ and do:
- Set ‘ARR[i]’ = ‘ARR[i]’ * ‘ARR[i]’.
- Sort the array ‘ARR’.
- Return ‘ARR’.
Approach: As the given array is sorted so we will use the Two-Pointer technique to generate a sorted array with squares.
Algorithm:
- First of all, take an array/list of size ‘N’ say ‘ANS’. It will be used to store the output array.
- We will fill the ‘ANS’ starting from back side, so initialize an integer ‘POS’ with ‘N - 1’.
- Initialize two integers say ‘START’ with 0 and ‘END’ with ‘N - 1’.
- If the absolute value of ‘ARR’ at ‘END’ is greater than the absolute value of ‘ARR’ at ‘START’ then do:
- Set the value of ‘ANS[POS]’ as square or ‘ARR[END]’.
- Move ‘END’ in the backward direction i.e. ‘END’ = ‘END’ - 1.
- Decrease the value of ‘POS’ by 1 as we have filled ‘ANS[POS]’ so now we will fill ‘ANS’ of ‘POS - 1’.
- Otherwise do:
- Set the value of ‘ANS[POS]’ as square or ‘ARR[START]’.
- Move ‘START’ in the forward direction i.e. ‘START’ = ‘START’ + 1.
- Decrease the value of ‘POS’ by 1 as we have filled ‘ANS[POS]’ so now we will fill ‘ANS’ of ‘POS - 1’.
- The loop will terminate when ‘POS’ will become less than 0. It will indicate that we have completely filled the ‘ANS’ array/list.
Similar problems