Squares of a Sorted Array Using Two Pointer Technique in Python

Problem Explanation

You are given a sorted array nums (in non-decreasing order).
Your task is to return a new array containing the squares of each number, also sorted in non-decreasing order.

Example:

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

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

---

Method Used: Two Pointer Technique

Idea

Even though the array is sorted, negative numbers become large when squared.
So we:

• Compare squares from both ends
• Place the largest square at the end of result

---

Why This Method?

• Time complexity: O(n)
• Space complexity: O(n)
• Avoids extra sorting
• Efficient and optimal

---

Python Code with Explanation

class Solution:
    def sortedSquares(self, nums):

Defines the function.

---

        n = len(nums)

Store the size of the array.

---

        result = [0] * n

Create a result array of same size.

---

        left = 0
        right = n - 1

Initialize two pointers:

• left at start
• right at end

---

        pos = n - 1

Position where the next largest square will be placed.

---

        while left <= right:

Loop until pointers meet.

---

            if abs(nums[left]) > abs(nums[right]):

Compare absolute values (since negatives can be larger when squared).

---

                result[pos] = nums[left] ** 2
                left += 1

If left is larger:

• Square it
• Place at pos
• Move left pointer

---

            else:
                result[pos] = nums[right] ** 2
                right -= 1

Otherwise:

• Take right value
• Square and place
• Move right pointer

---

            pos -= 1

Move position backward.

---

        return result

Return the final sorted squares array.

---

Complete Code

class Solution:
    def sortedSquares(self, nums):
        n = len(nums)
        result = [0] * n

        left = 0
        right = n - 1
        pos = n - 1

        while left <= right:
            if abs(nums[left]) > abs(nums[right]):
                result[pos] = nums[left] ** 2
                left += 1
            else:
                result[pos] = nums[right] ** 2
                right -= 1
            pos -= 1

        return result

---

Step-by-Step Example

Input:

[-4, -1, 0, 3, 10]

Steps:

• Compare ends → place largest square at end
• Repeat until complete

Output:

[0, 1, 9, 16, 100]

---

Key Takeaway

Using two pointers helps efficiently handle negative and positive values without sorting again.

---