Squares of a Sorted Array
Squares of a Sorted Array
Problem Description
Given an array sorted in ascending order, return an array of squared elements that remains sorted in ascending order.
Examples:
Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]Solution: Binary Search + Merged Arrays
// Author: Tecker 19/02/28
// Time: O(logN + N)
// Space: O(N)
vector<int> sortedSquares(vector<int>& A) {
if (A.size()==1) {
A[0]*=A[0];
return A;
}
// Find position where value >= 0
int pos = lower_bound(begin(A), end(A), 0) - begin(A);
vector<int> res(A.size());
// Move back one position so i points to possible negative number or head, j points to positive number or 0
int i= (pos>0) ? pos-1 : 0;
int j= i+1;
pos = 0;
// Merge from both ends toward center to create sorted array
while(i>=0 && j<=A.size()-1) {
int sub=abs(A[i])-A[j];
if (sub<0)
res[pos++] = pow(A[i--], 2);
else if (sub>0)
res[pos++] = pow(A[j++], 2);
else {
res[pos++] = pow(A[i--], 2);
res[pos++] = pow(A[j++], 2);
}
}
while (i>=0)
res[pos++] = pow(A[i--], 2);
while (j<=A.size()-1)
res[pos++] = pow(A[j++], 2);
return res;
}#binary-search