Squares of a Sorted Array

class Solution {
public:
    vector<int> computeSquares(vector<int>& numbers) {
        int size = numbers.size();
    
        vector<int> squared(size);
    
        int start = 0;
        int end = size - 1;
    
        for (int pos = size - 1; pos >= 0; pos--) {
            int squaredValue;
            if (abs(numbers[start]) < abs(numbers[end])) {
                squaredValue = numbers[end];
                end--;
            } else {
                squaredValue = numbers[start];
                start++;
            }
            squared[pos] = squaredValue * squaredValue;
        }
        return squared;
    }
};

In the provided C++ solution, the function computeSquares efficiently generates a sorted array of squares from a given sorted array numbers. This function utilizes a two-pointer approach:

• Declare start pointer at the beginning of the array and end pointer at the end.
• Create an output vector squared of the same size as the input array to store the squared values.
• Iterate from the end to the beginning of the squared vector and calculate square values in a descending order (largest square values first). This decision-making ensures that despite the negative numbers, when squared, the resultant values are positioned correctly in descending order.
• Evaluate the absolute values of the numbers at the start and end pointers. Square the larger value and move the respective pointer (either decrement end or increment start).
• Place the resulting square value in the current position of squared array (determined by pos).

By the end of this process, fill up the squared vector with numbers’ squares sorted in non-decreasing order without needing any additional sorting step, leveraging the information provided by the fact that the input array is already sorted. This approach provides a highly efficient solution to the problem, avoiding direct sorting which could increase computational complexity.

class Solution {
    public int[] squareAndSort(int[] values) {
        int length = values.length;
        int[] squaredValues = new int[length];
        int start = 0;
        int end = length - 1;
    
        for (int index = length - 1; index >= 0; index--) {
            int squared;
            if (Math.abs(values[start]) < Math.abs(values[end])) {
                squared = values[end];
                end--;
            } else {
                squared = values[start];
                start++;
            }
            squaredValues[index] = squared * squared;
        }
        return squaredValues;
    }
}

This Java solution addresses the problem of finding the squares of a sorted array and returning the result as a sorted array of these squares. Begin by defining the method squareAndSort inside the Solution class which takes an array values as its parameter.

• The method initializes an integer length to capture the length of the input array.
• An integer array squaredValues of the same length as values is created to store the squares of the elements.
• Two pointers, start and end, are initialized to point to the beginning and the end of the array respectively.

Using a for loop, iterate over the array from the last index to the first:

• In each iteration, compare the absolute values of the elements at the start and end pointers.
• The larger absolute value is squared and placed in the current position of the squaredValues array tracked by the index index.
• The pointer (either start or end) corresponding to the larger absolute value moves one step towards the center of the list.

The process continues until all elements of the original array have been squared and placed in the squaredValues array in descending order of their absolute values. The method then returns the squaredValues array containing the squares in non-decreasing order. This approach efficiently handles sorting while squaring by leveraging the property that the input array is already sorted.

class Solution:
    def squareAndSort(self, array: List[int]) -> List[int]:
        length = len(array)
        output = [0] * length
        start = 0
        end = length - 1
        for index in range(length - 1, -1, -1):
            if abs(array[start]) < abs(array[end]):
                square_val = array[end]
                end -= 1
            else:
                square_val = array[start]
                start += 1
            output[index] = square_val * square_val
        return output

This solution involves a function named squareAndSort which takes an array of integers as input and returns a new array where each integer is squared and the resultant array is sorted in ascending order.

The function starts by determining the length of the array and initializes another array output of the same length, filled initially with zeros. Two pointers, start and end, are used to traverse the array from the beginning and the end, respectively.

Using a reverse loop by indexing from the end to the start of the array, the function compares the absolute values of the elements at the start and end pointers. The element with the greater absolute value is squared and placed in the current position of the output array (targeted by index). This element's respective pointer (start or end) is then adjusted (incremented or decremented).

By iterating in this manner, the squared values are stored in reverse order, leading to a sorted array from smallest to largest square without needing an explicit sorting step. Once all elements have been processed, the output array is returned, containing the squared values in sorted order. Thus, this approach effectively combines the squaring and sorting operations in one pass through the data.