# Sorted Squares of a Sorted Array (Java) – Efficient Two-Pointer Approach

When working with sorted arrays, a seemingly simple transformation—like squaring each element—can break the order. This problem is a great example of how understanding patterns in data can help us design efficient algorithms.

🚀 Problem Statement

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

👉 Example

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

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

🤔 Why Is This Tricky?

At first glance, you might think:

“Just square every element and the array stays sorted.”

But that’s not true because:

• Negative numbers become positive when squared


• A large negative number (e.g., -10) becomes larger than smaller positives when squared

Example:

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

→ Squares → [49, 9, 4, 9, 121]  ❌ Not sorted

💡 Key Insight

The largest square value will always come from:

• Either the leftmost element (most negative), or


• The rightmost element (largest positive)

👉 This leads us to the two-pointer technique.

⚡ Optimal Approach (Two Pointers)

Steps:

1. Initialize two pointers:

• left = 0


• 
  

  right = n - 1

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


• 
  

  nums[left]^2 and nums[right]^2

  
  
  
  
  
  1. Place the larger square at the current position and move the corresponding pointer
  
  
  
  

🧑‍💻 Java Implementation

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--;

            }

            pos--;

        }



        return result;

    }

}

🔍 Dry Run

For:

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

⏱️ Complexity Analysis

✔ We traverse the array only once

⚠️ Naive Approach (Less Efficient)

Arrays.sort(nums);

for (int i = 0; i < nums.length; i++) {

    nums[i] = nums[i] * nums[i];

}

Arrays.sort(nums);

❌ Time Complexity: O(n log n) due to sorting

🎯 Why This Approach Works

• The array is already sorted


• The largest absolute values lie at the edges


• By comparing squares from both ends, we ensure correct placement

🏁 Conclusion

This problem highlights how:

• A simple transformation can break sorted order


• A clever two-pointer technique can restore efficiency

Mastering such patterns is essential for coding interviews and real-world problem solving.