Squares Of A Sorted Array - Leetcode Solution

The Squares of a Sorted Array problem on LeetCode is a relatively simple problem that can be solved in O(n) time complexity.

Problem Description:

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] Explanation: After squaring, the array becomes [16,1,0,9,100]. Sorting the array returns [0,1,9,16,100].

Example 2:

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

Solution:

One approach is to take the absolute values of each element of the input array and then square the absolute values. After that, we sort the squared array in non-decreasing order and return it.

Here is the implementation of the above approach:

def sortedSquares(nums: List[int]) -> List[int]:
    # Initialize left index and right index
    left = 0
    right = len(nums) - 1
    result = [0] * len(nums)
    index = len(nums) - 1
    
    # Loop from the right end of the array to the left end of the array
    # and fill the result array in non-decreasing order
    while index >= 0:
        if abs(nums[left]) > abs(nums[right]):
            result[index] = nums[left] * nums[left]
            left += 1
        else:
            result[index] = nums[right] * nums[right]
            right -= 1
        index -= 1
    return result

In this solution, we use two-pointers to iterate over the input array from both ends. The two pointers are left and right indices initialized as 0 and len(nums)-1, respectively. We also initialize another array called ‘result’. The result array is initialized as an array of zeros of the same length as the input array.

After initializing the indices and the result array, we use a while loop to iterate from the right end of the array to the left end of the array. Inside the while loop, we square the value of the element that has a larger absolute value and store it in the result array in non-decreasing order. If the absolute value of the element at the left pointer is greater than that of the right pointer, then we square the element at the left pointer and increment the left pointer. Otherwise, we square the element at the right pointer and decrement the right pointer. We keep decrementing the index until all values are filled in the result array.

Finally, we return the result array as an output.

The time complexity of this solution is O(n) and the space complexity is also O(n) where n is the length of the input array.

1