Solution Explanation: Squares of a Sorted Array

The problem asks to square each element in a sorted array and return a new array containing these squared elements, also sorted in non-decreasing order. A naive approach would involve squaring all elements and then sorting the resulting array, resulting in O(n log n) time complexity due to the sorting step. However, a more efficient O(n) solution is possible using a two-pointer approach.

Algorithm (Two Pointers):

1. Initialization: Create a new array ans of the same size as the input nums to store the results. Initialize two pointers, i and j, to point to the beginning and end of the nums array, respectively. Also, initialize a pointer k to point to the end of the ans array.

2. Iteration: Iterate while i <= j. In each iteration:

   • Square the elements at nums[i] and nums[j].
   • Compare the squared values. The larger squared value is placed at ans[k] (the end of the ans array).
   • Increment i if nums[i]^2 was larger; otherwise, decrement j.
   • Decrement k to move to the next position in ans.

3. Return: After the loop, ans will contain the squared elements in sorted order. Return ans.

Why this works:

Because the input array nums is sorted, the squares of the negative numbers (at the beginning of nums) will be in decreasing order, while the squares of the positive numbers (at the end of nums) will be in increasing order. The algorithm cleverly merges these two decreasing/increasing sequences into a single sorted sequence by comparing the squares of the elements at both ends and placing the larger square at the end of the result array.

Time Complexity: O(n) - The algorithm iterates through the input array once.

Space Complexity: O(n) - A new array of the same size as the input is created to store the results. If we disregard the space for the output array, the space complexity becomes O(1).

Code Examples (Python, Java, C++, Go, Rust, Javascript, PHP):

The provided code snippets in multiple languages implement this two-pointer algorithm. They all follow the same logic:

• Initialize an output array.
• Use two pointers (i, j) to track the start and end of the input array.
• Use a third pointer (k) to track the insertion point into the output array (working backwards from the end).
• Compare squared values at i and j, inserting the larger one into the output array.
• Increment/decrement pointers accordingly.

The Python example (slightly different due to the reverse indexing):

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        ans = []
        i, j = 0, len(nums) - 1
        while i <= j:
            a = nums[i] * nums[i]
            b = nums[j] * nums[j]
            if a > b:
                ans.append(a)
                i += 1
            else:
                ans.append(b)
                j -= 1
        return ans[::-1] # Reverse the list to get ascending order
 

The other language examples (Java, C++, Go, Rust, Javascript, PHP) directly build the sorted array in descending order then implicitly return a sorted array. The Python version explicitly reverses the result to match the problem statement's requirement of non-decreasing order.