ASSIGNMENT 18

📌 Problem Statement

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

---

🧪 Examples

Example 1

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

Example 2

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

---

❗ Why Not Just Square & Sort?

A simple solution:

square → sort

But that takes:

• ⏱ O(n log n) time

👉 We can do better: O(n)

---

💡 Optimal Approach: Two-Pointer Technique

🧠 Key Insight

• The array is sorted, BUT contains negative numbers
• Squaring negatives makes them positive → order breaks

👉 The largest square will always come from:

• Either the leftmost element OR
• The rightmost element

---

🔄 Algorithm Steps

1. Initialize:

   left = 0
   right = n - 1

1. Create result array of size n
2. Fill from end to start
3. Compare:

• abs(nums[left]) vs abs(nums[right])
  1. Place the larger square at the end

---

💻 Python Implementation

```python id="code1"
def sorted_squares(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

Example usage

nums = [-4, -1, 0, 3, 10]
print(sorted_squares(nums))

---

## 🧾 Output



```id="out1"
[0, 1, 9, 16, 100]

---

🔍 Dry Run (Quick Insight)

For:

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

• Compare |-4| and |10|
• Place 100 at end
• Move inward and repeat

---

⚡ Complexity Analysis

Metric	Value
Time Complexity	O(n)
Space Complexity	O(n)

---

🎯 Key Takeaways

• Sorting after squaring is not optimal ❌
• Use two-pointer technique for O(n) ✅
• Works because input array is already sorted 🔥

---

🏁 Conclusion

This problem is a great example of how understanding the data structure can lead to optimized solutions.

---