Squares of a Sorted Array

Clarify the problem:

• The problem requires squaring each element of a sorted array and returning a new array with the squares in sorted order.
• We need to implement a function that takes an array of integers as input and returns a new array with the squares in sorted order.

Analyze the problem:

• Input: An array of integers.
• Output: A new array with the squares of the integers in sorted order.
• Constraints: The input array is sorted in non-decreasing order.

Design an algorithm:

• We can use a two-pointer approach to solve this problem efficiently.
• Initialize two pointers, left and right, pointing to the start and end of the input array, respectively.
• Create an empty result array to store the squares in sorted order.
• While the left pointer is less than or equal to the right pointer:
  • Compare the absolute values of the elements at left and right.
  • If the absolute value at left is greater than or equal to the absolute value at right:
    • Square the value at left, append it to the result array, and increment the left pointer.
  • Otherwise:
    • Square the value at right, append it to the result array, and decrement the right pointer.
• Reverse the result array to obtain the squares in sorted order.
• Return the result array.

Explain your approach:

• We will implement a function called sortedSquares to solve the problem.
• The function will take an array of integers, nums, as input.
• We will initialize two pointers, left and right, pointing to the start and end of the input array.
• We will create an empty result array to store the squares in sorted order.
• While the left pointer is less than or equal to the right pointer, we will compare the absolute values at the left and right pointers.
• If the absolute value at left is greater than or equal to the absolute value at right, we will square the value at left, append it to the result array, and increment the left pointer.
• Otherwise, we will square the value at right, append it to the result array, and decrement the right pointer.
• Finally, we will reverse the result array to obtain the squares in sorted order and return it.

Write clean and readable code:

python

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

    while left <= right:
        left_val = abs(nums[left])
        right_val = abs(nums[right])

        if left_val >= right_val:
            result.append(left_val * left_val)
            left += 1
        else:
            result.append(right_val * right_val)
            right -= 1

    return result[::-1]

Test your code:

python

# Test case 1
nums = [-4, -1, 0, 3, 10]
# The squares are [16, 1, 0, 9, 100], and in sorted order, they become [0, 1, 9, 16, 100]
assert sortedSquares(nums) == [0, 1, 9, 16, 100]

# Test case 2
nums = [-7, -3, 2, 3, 11]
# The squares are [49, 9, 4, 9, 121], and in sorted order, they become [4, 9, 9, 49, 121]
assert sortedSquares(nums) == [4, 9, 9, 49, 121]

# Test case 3
nums = [0, 1, 2, 3, 4]
# The squares are [0, 1, 4, 9, 16], and they are already in sorted order
assert sortedSquares(nums) == [0, 1, 4, 9, 16]

I chose these test cases because they cover different scenarios:

• Test case 1 includes negative numbers in the input array.
• Test case 2 includes both negative and positive numbers in the input array.
• Test case 3 has the input array already sorted in non-decreasing order.

Optimize if necessary:

• The algorithm already has an optimal time complexity of O(N) since we process each element of the input array once.
• There is no further optimization possible for this problem.

Handle error cases:

• The code assumes that the input array is not None and has at least one element.
• If the input array is empty, the function will return an empty result array.

Discuss complexity analysis:

• Let N be the number of elements in the input array.
• The time complexity of the solution is O(N) since we process each element of the array once.
• The space complexity is O(N) as we create a result array of the same size as the input array.
• The code solves the problem optimally without any significant trade-offs.