Squares of sorted array in O(n) time 

Run Settings
LanguageC++
Language Version
Run Command
#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]<<" "; } }
Editor Settings
Theme
Key bindings
Full width
Lines