🔢 Squares of a Sorted Array – Python (Two Pointer Approach)

Hi All,

Today I solved an interesting problem: Squares of a Sorted Array using an efficient approach.

---

📌 Problem Statement

Given a sorted array nums (in non-decreasing order), return a new array of the squares of each number, also sorted.

---

🔍 Examples

Example 1:

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

Output:

[0, 1, 9, 16, 100]

---

Example 2:

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

Output:

[4, 9, 9, 49, 121]

---

💡 Problem Insight

👉 Even though the array is sorted:

• Negative numbers become positive after squaring
• So the result is not automatically sorted

---

💡 Approach

🔹 Method 1: Brute Force

• Square all elements
• Sort the array

❌ Time Complexity: O(n log n)

---

🔹 Method 2: Two Pointer (Optimal)

👉 Key idea:

• Largest square will be from either:
  • Leftmost (negative large)
  • Rightmost (positive large)

---

🧠 Step-by-Step Logic

1. Initialize:

   • left = 0
   • right = n - 1
   • result array of size n

2. Compare:

   • nums[left]^2 vs nums[right]^2

3. Place larger value at the end of result

4. Move pointers accordingly

---

💻 Python Code

def sortedSquares(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

---

🔍 Dry Run

For:

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

Steps:

• Compare 4² and 10² → place 100
• Compare 4² and 3² → place 16
• Continue...

Final Output:

[0, 1, 9, 16, 100]

---

🖥️ Sample Output

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

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

---

⚡ Complexity Analysis

• Time Complexity: O(n) ✅
• Space Complexity: O(n) ✅

---

🧠 Why this is important?

• Uses two pointer technique
• Avoids unnecessary sorting
• Common interview pattern

---

✅ Conclusion

This problem helped me understand:

• Handling negative numbers in sorted arrays
• Two pointer optimization
• Efficient array transformations

🚀 Must-know problem for coding interviews!

---