CA 18 - Squares of a Sorted Array

Problem Statement: here

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

Solution:

def sortedSquares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    pos = n - 1
    while left <= right:
        if abs(nums[left]) > abs(nums[right]):
            result[pos] = nums[left] * nums[left]
            left += 1
        else:
            result[pos] = nums[right] * nums[right]
            right -= 1
        pos -= 1
    return result

• We have to square every number and return the result in sorted order.
• The largest square will come from either the leftmost element (big negative) or the rightmost element (big positive). So we use two pointers.

Dry run
Input:
[-4, -1, 0, 3, 10]

Start:
left = 0, right = 4
result = [0,0,0,0,0]

---

Compare |−4| vs |10| → 10 bigger
→ 100 goes at end
result = [0,0,0,0,100]
right--

---

Compare |−4| vs |3| → 4 bigger
→ 16
result = [0,0,0,16,100]
left++

---

Compare |−1| vs |3| → 3 bigger
→ 9
result = [0,0,9,16,100]
right--

---

Compare |−1| vs |0| → 1 bigger
→ 1
result = [0,1,9,16,100]
left++

---

Compare |0| vs |0| → 0
→ 0
result = [0,1,9,16,100]

---

Final answer:
[0, 1, 9, 16, 100]