Given an integer array sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Overview

Need to square each element and save it in a new array sorted. The tricky part is when the array has negative numbers. It is worth mentioning that the input array is sorted, we will use that to our advantage.

Flow Diagram - Brute Force

We went through each element and then at the end we sorted the array. This solution also works with unsorted arrays. Since we know that the input array is sorted. There is a more optimal solution.

Time Complexity

To solve this problem, we need to iterate through the array once, that leads us to a time complexity of O(n). The input array is already sorted so it no extra complexity is accounted for.

Space Complexity

The space complexity is O(n) as a new array needs to be created to store the squared values.

Java Source Code

Solution - Brute Force

public int[] bruteForce(final int[] inputArray) {
        final var sortedSquareArray = new int[inputArray.length];

        for(int i = 0;i<inputArray.length;i++) {
            sortedSquareArray[i] = (int) Math.pow(inputArray[i],2);
        }

        Arrays.sort(sortedSquareArray);

        return sortedSquareArray;
    }

Flow Diagram - Optimal

No need to sort at the end, thus having better time complexity. The strategy here is to note:

• Array is sorted
• Smaller negative numbers result in higher squared number.
• Compare the smallest negative number with the largest number. Who ever is largest gets to go into the position in the array
• Repeat previous point until we traversed the input array

Java Source Code

Solution - Optimal

public int[] optimal(final int[] inputArray) {
            final var sortedSquareArray = new int[inputArray.length];

            var startIndex = 0;
            var endIndex = inputArray.length-1;

            for(int i = inputArray.length-1;i>=0;i--) {
                var sortedArrayElement = 0;
                if(Math.abs(inputArray[endIndex]) > Math.abs(inputArray[startIndex])) {
                    sortedArrayElement = (int) Math.pow(inputArray[endIndex],2);
                    endIndex--;
                } else {
                    sortedArrayElement = (int) Math.pow(inputArray[startIndex],2);
                    startIndex++;
                }

                sortedSquareArray[i] = sortedArrayElement;
            }

            return sortedSquareArray;
        }

Conclusion

Sometimes you need time away to sort things out in your head. It makes everything clearer

Jojo Moyes