Please see github.com/anusha-murali for all of my repositories.
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.