Ordered squares of an ordered integer array

Question

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;
}

• vnp: 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.
• Frank: 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.)
• vnp: Sorry, minimal abs.
• slepic: @vnp no need for abs, just take the first nonnegative element and see how its sum with its previous element compares to zero.
• Toby Speight: The problem statement is very similar to LeetCode 977, as referenced in Squares of a sorted array, maintaining non-decreasing order.

Answer 1

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;
}

Answer 2

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.

• Frank: How would you code this so it's \$O(n)\$?
• CiaPan: @Frank Please see my answer.

Answer 3

Here is an example of an \$\mathcal O(n)\$ - time solution.

import java.io.*;
public class SortedSquaresOfSortedIntegerArray
{
 public static int findIdxOfFirstPositive(int[] a)
 {
 for(int i = 0; i < a.length; i ++)
 if(a[i] > 0)
 return i;
 // assuming a[] is in increasing order, positive
 // values should be to the right of all negative;
 // so if there is no positive in the array, let's
 // pretend they are just past the end of the array
 return a.length;
 }
 public static int[] makeSquares(int[] a)
 {
 int posIdx = findIdxOfFirstPositive(a);
 int negIdx = posIdx - 1;
 int sqrIdx = 0;
 int[] squares = new int[a.length];
 // while there are still unhandled negative and positive
 // input values, take the first one from each sequence and
 // compare their absolute values to choose the 'smaller'
 // one (that is, the one resulting in a smaller square);
 // delete it from its sequence and append its square to a result
 while(negIdx >= 0 && posIdx < a.length)
 {
 if(-a[negIdx] < a[posIdx])
 {
 squares[sqrIdx ++] = a[negIdx] * a[negIdx];
 negIdx --;
 }
 else
 {
 squares[sqrIdx ++] = a[posIdx] * a[posIdx];
 posIdx ++;
 }
 }
 // at least one of the sequences is empty now,
 // so handle those negative (if there are any left)...
 while(negIdx >= 0)
 {
 squares[sqrIdx ++] = a[negIdx] * a[negIdx];
 negIdx --;
 }
 // ...or positive
 while(posIdx < a.length)
 {
 squares[sqrIdx ++] = a[posIdx] * a[posIdx];
 posIdx ++;
 }
 return squares;
 }
 // testing routines
 public static int findDiffIdx(int[] a, int[] b)
 {
 // find the difference (assuming the arrays lengths are equal);
 // return the index of the first difference found
 // or (-1) if all respective elements are equal
 for(int i = 0; i < a.length; i ++)
 if(a[i] != b[i])
 return i;
 return -1;
 }
 public static void printArray(String name, int[] arr)
 {
 System.out.print(name);
 for(int i = 0; i < arr.length; i ++)
 System.out.printf(i == 0 ? " %d" : ", %d", arr[i]);
 System.out.println();
 }
 public static void testResult(int[] input, int[] expected, int[] result)
 {
 printArray("input...:", input);
 printArray("expected:", expected);
 printArray("result..:", result);
 if(input.length != expected.length)
 {
 System.out.println("Error in test data: length different from input.");
 }
 else if(input.length != result.length)
 {
 System.out.println("Error in result data: length different from input.");
 }
 else
 {
 // all three arrays lengths tested equal
 int diffIdx = findDiffIdx(expected, result);
 if(diffIdx == -1)
 System.out.println("OK");
 else
 System.out.printf("Error: unexpected value at index %d.\n", diffIdx);
 }
 System.out.println();
 }
 public static void main(String[] args)
 {
 // do some tests, print results
 // some tests are intentionally wrong
 int[] input;
 int[] expected;
 int[] result;
 // length error - empty input
 input = new int[] {};
 expected = new int[] {4, 9};
 result = makeSquares(input);
 testResult(input, expected, result);
 // length error - non-empty input
 input = new int[] {2, 3};
 expected = new int[] {9};
 result = makeSquares(input);
 testResult(input, expected, result);
 // test value error
 input = new int[] {1, 7};
 expected = new int[] {1, 7};
 result = makeSquares(input);
 testResult(input, expected, result);
 // singleton, negative
 input = new int[] {-8};
 expected = new int[] {64};
 result = makeSquares(input);
 testResult(input, expected, result);
 // singleton, positive
 input = new int[] {11};
 expected = new int[] {121};
 result = makeSquares(input);
 testResult(input, expected, result);
 // positives
 input = new int[] {3, 5, 6, 9};
 expected = new int[] {9, 25, 36, 81};
 result = makeSquares(input);
 testResult(input, expected, result);
 // negatives
 input = new int[] {-5, -3, -2, 0};
 expected = new int[] {0, 4, 9, 25};
 result = makeSquares(input);
 testResult(input, expected, result);
 // both
 input = new int[] {-5, -3, -2, 4, 5};
 expected = new int[] {4, 9, 16, 25, 25};
 result = makeSquares(input);
 testResult(input, expected, result);
 }
}

The processing algorithm is implemented in the makeSquares method.

The first step is finding the first positive value in the input array (done by method findIdxOfFirstPositive). Due to the assumptions, that will be the smallest positive in the input array.

Then we can walk with two indices from that point: upwards, to scan positive values; and downwards, to scan negative ones (here 'negative' include zero). This way we scan both sequences in increasing order of absolute values.

At each step we compare the negated negative value (i.e., its absolute value) with the positive one, and choose the smaller one. Then we append its square to the result array. This means we virtually merge the two sequences in increasing order of absolute values and we get an increasing sequence of squares as a result.

When one of those sequences gets exhausted we proceed on the remaining one. In case of an input array with either negative or positive values only, the first loop gets skipped and we process all the negative or all the positive data with the respective loop. In a pathological case of both sequences empty, which means the input array is empty, all three loops get skipped due to all three while conditions being false.

Now we can see the makeSquares() routine performs

• a linear search in findIdxOfFirstPositive() – each element is tested in order until the positive one is found, and none is tested more than once,
• then a linear processing – we go through three loops, each iteration of each loop either decreases negIdx or increases posIdx variable, and those indices scan two disjoint segments of an array, so every element is visited exactly once which implies all three loops perform exactly \$ n \$ iterations in total.

As a result makeSquares() performs at least \$n+1\$ and at most \2ドルn\$ elementary steps, which are:

1. testing an element, or
2. comparing two elements and saving a square of one of them, or
3. saving a square of one of remaining elements,

all of them bounded by some constant time.
Conclusion: the routine's time complexity is indeed \$\mathcal O(n).\$

• radarbob: The ambition is impressive. The testing is laudable; coverage is comprehensive and thoughtful. Yet this code will be rewritten given a real world code base because the target code is so intimately infused with the testing and UI support code. Because the code works - the proof is in the testing! - I sincerely think this code is therefore a good exercise in refactoring vice a blank-page rewrite; i.e. changing its form while preserving its correct/working behavior.
• chux: @CisPan, Good initial example of an O(n) time solution.
• CiaPan: @radarbob Sure, the working code and testing code would be better separated into two classes. However, I do not have any Java compiler at hand, so I used GDB online to verify my code prior to posting it here, and I haven't realized it allows you to work with multiple files. :) Anyway, separating it should be quite easy—just cut the code in half at the // testing routines comment. :D
• CiaPan: @radarbob An additional note for readers: testing alone never proves correctness. A test just... tests a single, specific case. We usually may reasonably assume some regularity in the program's behavior and, consequently, generalize correctness in some specific cases spread across the domain onto the whole domain. But an actual proof, if ever possible, follows from the thorough code analysis, together with the domain definition (expected input data range) as well as execution environment limitations.
• radarbob: testing alone never proves correctness -> Yep. It sounds banal but is profoundly important. So let me change the proof is in the testing! to the hope is in the testing!