Sharmila devi

Posted on Mar 24

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

#algorithms #dsa #java #leetcode

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:

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]

Step	Left	Right	Chosen Square	Result
1	-4	10	100	[_, _, _, _, 100]
2	-4	3	16	[_, _, _, 16, 100]
3	-1	3	9	[_, _, 9, 16, 100]
4	-1	0	1	[_, 1, 9, 16, 100]
5	0	0	0	[0, 1, 9, 16, 100]

⏱️ Complexity Analysis

Aspect	Complexity
Time	O(n)
Space	O(n)

✔ 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.

Forem