Sorting squares of an integer array

I had this question in an interview recently. Given a sorted array of integers, return a list of those integers squared, with the squares sorted. So given an array of these numbers:

-5, -3, 1, 2, 4


the result should be this:

1 4 9 16 25


I came up with this solution using Java 8 streams, but is there a way to do this without the call to Array.sort?

public static int[] sortedSquares(int[] arr) {
arr = Arrays.stream(arr).map(i -> i * i).toArray();
Arrays.sort(arr);
return arr;
}

• Yes, there is a linear solution. Find the minimal element. Its square is guaranteed to be minimal. Now think of two indices traversing the array to the left and to the right from the minimal element, producing squares in a desired order. – vnp Jun 4 at 1:20
• In the example, the minimal element of the original array is -5, but its square is +25, which is not the minimal square (which would be +1 squared = 1), so how would this work?. (The original array is guaranteed to be sorted, by the way. At least that's the way the problem was stated to me.) – Frank Jun 4 at 1:33
• Sorry, minimal abs. – vnp Jun 4 at 1:40
• @vnp no need for abs, just take the first nonnegative element and see how its sum with its previous element compares to zero. – slepic Jun 4 at 17:33

One way to be more concise is to use the Stream.sorted() method right in the stream:

public static int[] sortedSquares(int[] arr) {
arr = Arrays.stream(arr).map(i -> i * i).sorted().toArray();
return arr;
}

• At this point is there any point in not just using return Arrays. – Peilonrayz Jun 4 at 11:10
• Yes that's viable. – tinstaafl Jun 4 at 12:29

For an interview, this is bad code. It is $$\O(n \log n)\$$. But it can be done in $$\O(n)\$$ time. Your code does not show your skills in that direction. Also, many interviewers (justifiably) will be unhappy for using streams. Streams may look cute but at scale like Gmail, they cause performance problems.

• How would you code this so it's $O(n)$? – Frank Jul 9 at 4:44