Squares of sorted array in O(n) time
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
#include <iostream>
using namespace std;
int main() {
int arr[] = {-2, -1, 0, 2, 3};
int n = sizeof(arr)/sizeof(arr[0]);
int pos = -1;
int count = 0;
for(int i=0 ; i<n; i++){
if(arr[i]>0){
pos = i;
count++;
break;
}
}
int sqr[n];
if(pos==-1){
for(int i=n-1; i>=0; i--){
sqr[(n-1)-i] = arr[i] * arr[i];
}
}
else if(count == n-1){
for(int i=0; i<n; i++){
arr[i] = arr[i]*arr[i];
}
}else if(pos != -1 && count != n-1){
int j=pos-1;
int k = 0;
while(j>=0 && pos<n){
if((arr[j]*arr[j])>(arr[pos]*arr[pos])){
sqr[k] = arr[pos]*arr[pos];
pos++;
k++;
}else if((arr[pos]*arr[pos])>(arr[j]*arr[j])){
sqr[k] = arr[j]*arr[j];
k++;
j--;
}else {
sqr[k] = arr[j]*arr[j];
k++;
sqr[k] = arr[pos]*arr[pos];
pos++;
j--;
k++;
}
}
while(j>=0){
sqr[k] = arr[j]*arr[j];
j--;
k++;
}
while(pos<=n-1){
sqr[k] = arr[pos]*arr[pos];
pos++;
k++;
}
}
for(int i=0 ; i<n;i++){
cout<<sqr[i]<<" ";
}
}
Cpp
INFO