Efficiently squaring each element in a sorted array, keeping it sorted
It can be done in O(n) time. Split your array into two logical parts. Positive and negative. Then apply square to each element in both arrays. Then merge the arrays( merging can be done in O(n) ), but merge the array with previously negative integers in reverse order, since its values will be reversed.