Squares of a Sorted Array — Understanding the Two Pointer Trick

This problem looks simple at first, but it hides a classic two-pointer pattern.

Let’s break it down clearly.

Problem Understanding

You are given a sorted array of integers.
The array may contain negative numbers.

Your task:

Return a new array of the squares of each number, sorted in non-decreasing order.

Example

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

Why Simple Squaring Doesn’t Work

If you square each element directly:

[-4, -1, 0, 3, 10] → [16, 1, 0, 9, 100]

This is not sorted, because negative numbers become large positives after squaring. So we need a smarter approach.

Key Insight

Although the array is sorted the largest square will always come from either the leftmost (most negative) or the rightmost (largest positive)

That’s the signal to use two pointers.

Two Pointer Approach

Pointer Setup

• left → start of array
• right → end of array
• j → end of result array (to fill largest squares first)

C++ Code

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> res(nums.size(), 0);

        int left = 0;
        int right = nums.size() - 1;
        int j = nums.size() - 1;

        while (left <= right) {
            if (abs(nums[left]) > abs(nums[right])) {
                res[j--] = nums[left] * nums[left];
                left++;
            } else {
                res[j--] = nums[right] * nums[right];
                right--;
            }
        }
        return res;
    }
};

How Pointer Movement Works

1. Compare abs(nums[left]) and abs(nums[right])
2. The larger absolute value gives the larger square
3. Place it at the end of result array
4. Move the corresponding pointer inward
5. You never need sorting again.

Example Walkthrough

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

Steps:

Compare |-4| and |10| → take 10²

Compare |-4| and |3| → take (-4)²

Continue until pointers cross

Result builds from right to left.

Complexity

Time    O(n)
Space   O(n)

-> Faster than sorting
-> Uses sorted input efficiently

What I Learned

1. Sorted array + opposite ends → think two pointers
2. Negative values matter when squaring
3. Build result from largest to smallest
4. Avoid unnecessary sorting

Pattern Takeaway

If a problem has:

sorted array

transformation (square, absolute, etc.)

order must be preserved

👉 Try two pointers from both ends

Final Thoughts

This problem strengthened my understanding of pointer comparison logic , building results backward,choosing the right pattern instead of brute force

It’s a perfect beginner two-pointer problem and a must-solve if you’re learning arrays 🚀