algoadvance

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in non-decreasing order.

Clarifying Questions:

1. Can I assume that the input array will always contain at least one element as per the constraints?
2. Are there any specific inputs that I should consider, like arrays that only contain non-negative or non-positive numbers?

Strategy:

1. Two-Pointer Approach:
   • Since the array is sorted, negative numbers, when squared, will become positive and might end up larger than some of the positive numbers.
   • Use two pointers: one at the beginning (left) and one at the end (right) of the array.
   • Compare the absolute values of the elements at these pointers.
   • Place the larger square at the current end of the result array and move the corresponding pointer inward.
   • Continue this process until all elements have been processed.

This method is efficient and ensures that we only pass through the array once, making it an O(n) time complexity solution.

Code:

def sortedSquares(nums):
    # Two pointers
    left, right = 0, len(nums) - 1
    result = [0] * len(nums)
    position = len(nums) - 1
    
    # Process the elements from both ends towards the middle
    while left <= right:
        left_square = nums[left] * nums[left]
        right_square = nums[right] * nums[right]
        
        if left_square > right_square:
            result[position] = left_square
            left += 1
        else:
            result[position] = right_square
            right -= 1
        position -= 1
    
    return result

Time Complexity:

• Time Complexity: O(n) - We traverse the entire array once with two pointers.
• Space Complexity: O(n) - We use an additional array to store the squared values.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?