Squares of a Sorted Array - CA18

My Thinking and Approach

---

Introduction

In this problem, I was given a sorted array of integers and asked to return a new array containing the squares of each number, also sorted in non-decreasing order.

---

Problem Statement

• Given a sorted array nums

• Return an array of squares of each element

• Conditions:

  • Output must be sorted
  • Input array is already sorted

---

My Initial Thought

At first, I considered:

• Squaring all elements
• Sorting the result

But this approach takes extra time due to sorting.

---

Key Observation

Even though the array is sorted:

• Negative numbers become positive after squaring
• Larger absolute values produce larger squares

So, the largest square will be at either end of the array.

---

Optimized Approach

I decided to use two pointers.

Logic:

• Compare absolute values at both ends
• Place the larger square at the end of result array
• Move pointers accordingly

---

My Approach (Step-by-Step)

1. Initialize:

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

1. While left <= right:

• Compare abs(nums[left]) and abs(nums[right])
• Place larger square at result[index]
• Move pointer and decrease index

---

Code (Python)

Below is the implementation clearly separated inside a code block:

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

        left = 0
        right = n - 1
        index = n - 1

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

        return result

---

Example Walkthrough

Input:

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

Steps:

• Compare -4 and 10 → 100
• Compare -4 and 3 → 16
• Compare -1 and 3 → 9
• Continue filling result

Output:

[0, 1, 9, 16, 100]

---

Complexity Analysis

Type	Complexity
Time Complexity	O(n)
Space Complexity	O(n)

---

Key Takeaways

• Sorted input can be used for optimization
• Two pointer technique is effective
• Avoid unnecessary sorting

---

Conclusion

This problem helped me understand how to use two pointers to efficiently process sorted arrays and avoid extra sorting.

---