Question:

You are given an array of integers that is sorted in non-decreasing order. Write a function to return a new array containing the squares of each number in the input array, in non-decreasing order.

Implement the function sortedSquares(nums: List[int]) -> List[int]:

Input

• nums: An array of integers (1 <= len(nums) <= 10^4) in non-decreasing order. Each integer is in the range [-10^4, 10^4].

Output

• A new array containing the squares of each number in the input array, in non-decreasing order.

Example

sortedSquares([-4, -2, 0, 3, 5])

Output: [0, 4, 9, 16, 25]

Answer:

To solve this problem, we can use the two-pointer technique. The basic idea is to use two pointers, one starting from the beginning and the other from the end of the array. We compare the square of the value at each pointer and store the larger value at the end of a new result array. We move the pointers accordingly and repeat until we have considered all the elements in the input array.

Here is the step-by-step solution:

1. Initialize two pointers, left and right, pointing to the start and end of the input array nums.
2. Initialize a new array result to store the squares of each number.
3. Start a loop until left <= right, indicating we haven't considered all the elements in nums.
4. Calculate the square of the values at nums[left] and nums[right].
5. Compare the squares: if nums[left] square is greater than or equal to the square of nums[right], we add nums[left] square to the beginning of result and increment left pointer by 1.
6. Otherwise, we add nums[right] square to the beginning of result and decrement right pointer by 1.
7. Repeat steps 4-6 until left and right pointers cross each other or meet in the middle.
8. Finally, return the reversed result array as the output.

The runtime complexity of this solution is O(n), where n is the length of the input array nums. Here is the implementation in Python:

def sortedSquares(nums):
    left = 0
    right = len(nums) - 1
    result = []

    while left <= right:
        square_left = nums[left] ** 2
        square_right = nums[right] ** 2

        if square_left >= square_right:
            result.insert(0, square_left)
            left += 1
        else:
            result.insert(0, square_right)
            right -= 1

    return result[::-1]

Now, let's test the function with the example given in the question:

print(sortedSquares([-4, -2, 0, 3, 5]))

Output:

[0, 4, 9, 16, 25]

The function correctly returns the squared values of each element in the input array in non-decreasing order.