Squares of a Sorted Array

This is an elegant LeetCode problem (Problem # 977), which demonstrates the power of two pointers to reduce runtime.

Problem:

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]. After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11]

Output: [4,9,9,49,121]

Solution

Observation: Since negative numbers are found in asending order at the beginning of the array, their magnitude are larger initially and then they gradually decrease. When the numbers become positive, the magnitudes will gradually increase as we move toward the end of the array.

Therefore, we use two pointers, namely left and right to traverse from the beginning of the array and end of the array respectively. We will compare their magnitudes (absolute values) and place them at the right positions in the output array called squares, which is initialized with zeroes.

def sortedSequence(nums):
    squares = [0]*len(nums)
    left = 0
    right = len(nums) - 1
   
    for i in range(len(nums)):
        if abs(nums[left]) > abs(nums[right]):
            squares[len(nums)-i-1] = nums[left]**2
            left += 1
        else:
            squares[len(nums)-i-1] = nums[right]**2
            right -= 1

    return squares

Runtime: Since the for loop is iterating $n$ times, the runtime is $O(n)$. The space complexity is also $O(n)$, as we are using a list of size $n$ to store the squares.

Back to Two Pointers Problems

Anusha Murali

Squares of a Sorted Array

anusha-murali.github.io