Squares of a Sorted Array – CA18

My Thinking and Approach

Introduction

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

At first, it looked very easy, but then I realized that squaring negative numbers changes their order.

---

Problem Understanding

• Input array is already sorted
• Square each element
• Return the result in sorted order

---

My Initial Thought

First, I thought:

• Square every element
• Then sort the array

Approach

• Traverse array → square each element
• Use sorting

But this takes:

• Time: O(n log n)

So I tried to find a better approach.

---

Key Observation

I noticed:

• Negative numbers become positive after squaring

• The largest square values come from:

  • Either the left end (large negative numbers)
  • Or the right end (large positive numbers)

---

Optimized Approach (Two Pointer)

Instead of sorting, I used the two-pointer technique.

Idea

• Compare squares from both ends
• Place the larger one at the end of result array

---

My Approach

• Initialize:

  • left = 0
  • right = n - 1
  • pos = n - 1 (to fill result from end)

Steps

1. Compare square of nums[left] and nums[right]
2. Place the larger square at result[pos]
3. Move pointer accordingly
4. Decrement pos
5. Repeat until all elements are processed

---

Code (Java)

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

        int left = 0, right = n - 1;
        int pos = n - 1;

        while (left <= right) {
            int leftSq = nums[left] * nums[left];
            int rightSq = nums[right] * nums[right];

            if (leftSq > rightSq) {
                result[pos--] = leftSq;
                left++;
            } else {
                result[pos--] = rightSq;
                right--;
            }
        }

        return result;
    }
}

---

Example Walkthrough

Example 1

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

Steps:

• Compare (-4)² = 16 and (10)² = 100 → place 100
• Compare (-4)² = 16 and (3)² = 9 → place 16
• Compare (-1)² = 1 and (3)² = 9 → place 9
• Continue...

Output:
[0, 1, 9, 16, 100]

---

Example 2

Input:
[-7, -3, 2, 3, 11]

Output:
[4, 9, 9, 49, 121]

---

Complexity Analysis

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

---

Key Takeaways

• Sorting is not always required if the array is already structured
• Two-pointer technique is very powerful
• Think about how transformations affect order

---

Conclusion

This problem helped me understand how to optimize beyond the obvious solution. Instead of using sorting, using two pointers gave a much better solution.

It improved my thinking about how data behaves after transformations like squaring.