Квадраты чисел в отсортированном массиве

Задача: дан массив А целых чисел отсортированныз в неубывающем порядке. Вернуть массив, который содержит квалраты этих чисел, тоже не в возрастающем порядке.

Оригинал:

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

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

1. 1 <= A.length <= 10000
2. -10000 <= A[i] <= 10000
3. A is sorted in non-decreasing order.

Источник: https://leetcode.com/problems/squares-of-a-sorted-array/submissions/

Решение:
Здесь хитрость в том, что квадрат ы отрицательных чисел положительны, поэтому их нужно вставить среди квадратов положительных чисел.

class Solution {
    public int[] sortedSquares(int[] arr) {
        // проверка на ноль
        if (arr==null) return null;
        if (arr.length==0) return arr;
       
        // result will be of the same size at the original array
        int[] result = new int[arr.length];
       
        // проверка вырожденного случая
        if (arr.length==1) {
            result[0] = arr[0]*arr[0];
            return result;
        }
       
        // ставим указатель на текущую ячейку результата (массив квадратов)
        int currindex=0;
       
        // найдём индекс в исходном массиве, где меняется знак чисел
        // changingIndex - индекс последнего отрицательного числа перед 0 или положительным
        int changingIndex = findIndex(arr, 0, arr.length-1);
       
        // знак не менялся
        if (changingIndex==-1) {
            boolean isPositive = false;
            if (arr[0]>=0) isPositive=true; // все неотрицат. числа в исходнике
            if (isPositive) { // просто считаем квадраты
                for (int i = 0; i<arr.length; i++) {
                    result[currindex++]=arr[i]*arr[i];
                }
            } else { // все только отрицательыне числа
                // считаем квадраты, начиная с последнего
                for (int i = arr.length-1; i>=0; i--) {
                    result[currindex++]=arr[i]*arr[i];
                }
            }
// возвращаем результат, тут больше делать нечего
            return result;
        }
    
// знак менялся
        // если в исходнике есть 0, найдём индекс самого первого
        while (changingIndex>0 && arr[changingIndex]==0) { changingIndex--;}
      
        // от первого нуля выходят два указателя:
        // один идёт влево по отрицательным числам до головы массива
        // второй - вправо по неотриц. числам до хвоста массива
        int goleft = changingIndex;
        int goright = changingIndex+1;
       
        while(goleft>=0 && goright<arr.length) {
            if (Math.abs(arr[goleft])<arr[goright]) {
                result[currindex++]=arr[goleft]*arr[goleft];
                goleft--;
            } else {
                result[currindex++]=arr[goright]*arr[goright];
                goright++;
            }
        }
        if (goleft<0&&goright<arr.length) {
            for (int i = goright; i < arr.length; i++) {
                result[currindex++]=arr[i]*arr[i];
            }
        }
        if (goright>=arr.length && goleft>=0) {
            for (int i = goleft; i>=0; i--) {
                result[currindex++]=arr[i]*arr[i];
            }
        }
        return result;
       
    }

// вспомогательная процедура, которая бинарным поиском находит
// индекс наибольшего отрицательного числа,
// т.е. которое непосредственно перед нулём.
// Если нет перехода от отрицательных к 0/неотрицательным, то возвращает -1
    public int findIndex(int[] arr, int start, int end) {
        while (start<end) {
            int mid = (start + end)/2;
             if (mid+1<arr.length) { // есть ли пара для умножения?
                int num = arr[mid]*arr[mid+1];
// если произведение двух соседних чисел отрицательно, то в исходнике нет нулей,
// и мы попали в пару -+
                if (num<=0) {
// число * 0, причем 0 в индексе mid, а другое число тоже может быть 0
                    if (num==0 && arr[mid]==0) return mid;
// число * 0, причем 0 в индексе mid+1
                    if (num==0 && arr[mid+1]==0) return mid+1;
// а вот и пара -+
                    if (num<0 && arr[mid]<0) return mid;
                }

// либо оба отрицательные, либо  оба положительные
                if (num>0 && arr[mid]>=0) {
// если оба положительные, то правая граница поиска сдвигается влево на  mid
// чтобы
                    end = mid;
                } else {
// если оба отрицательные, то левая граница поиска сдвигается влево на  mid +1
                    start=mid+1;
                } // конец проверки положительного произведения
            } // конец проверки, есть ли пара для умножения
        } // конец while, ничего не нашли, возвращаем -1
        return -1;
    }
}

Complexity Analysis

• Time Complexity: $O(N)$, where $N$ is the length of arr.
• Space Complexity: $O(N)$.

Testing results according to leetcode:

Runtime: 1 ms, faster than 100.00% of Java online submissions for Squares of a Sorted Array.
Memory Usage: 40.3 MB, less than 98.17% of Java online submissions for Squares of a Sorted Array.