The O(n) Club: Squares of a Sorted Array—Why Squaring Wrecks Your Sort (and How Two Pointers Play Cleanup)

The O(n) Club: Squares of a Sorted Array—Why Squaring Wrecks Your Sort (and How Two Pointers Play Cleanup)

⚡ TL;DR

Got a sorted array? Need a sorted array of their squares? Here’s the lazy way: square everything and sort it. Here’s the genius way: two pointers, fill from both ends. Welcome to O(n) efficiency with Java simplicity.

// Brute-force special
int[] squares = Arrays.stream(nums).map(x -> x * x).toArray();
Arrays.sort(squares);

🧠 How Devs Usually Mess This Up

First instinct: “Hey, if the original is sorted, the squares must be, right?” That works until negative numbers get involved and throw your sorting dreams under the bus. Example: [-4, -1, 0, 3, 10] turned into [16, 1, 0, 9, 100]. See, it’s as sorted as my desk after a 48-hour hackathon. So most folks reach for sort() and pray. But if you do that, you can wave goodbye to O(n) and any “wow” points in interviews.

🔍 What’s Actually Going On

Let’s break it down with something everyone understands—playground bullies. Consider the negatives (left end) and positives (right end) as rival teams. Their absolute values compete to see who delivers the biggest square. You compare the leftmost and rightmost numbers, square the bigger (by absolute value), and stick it at the end of the results. Then you move the winning pointer inward. This isn’t just clever—it’s cut-from-the-interview-poster clever. Rinse, repeat, glory in your O(n) victory.

🛠️ PseudoCode

• Start two pointers: left = 0, right = nums.length - 1.
• Prepare an empty result array, same length as nums.
• For i = result.length - 1 down to 0:
  • If Math.abs(nums[left]) > Math.abs(nums[right]):
    • result[i] = nums[left] * nums[left]; left++;
  • Else:
    • result[i] = nums[right] * nums[right]; right--;
• Repeat until left > right. Result array is now beautifully sorted. Bask in your efficiency.

💻 The Code

public int[] sortedSquares(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    int left = 0, right = n - 1;
    for (int i = n - 1; i >= 0; i--) {
        if (Math.abs(nums[left]) > Math.abs(nums[right])) {
            result[i] = nums[left] * nums[left];
            left++;
        } else {
            result[i] = nums[right] * nums[right];
            right--;
        }
    }
    return result;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Don’t trust the input to be all positive: negatives squared make big numbers.
• Watch for single element arrays, all zeros, duplicates, or only negatives—edge case fiesta.
• Time: O(n), one glorious pass. Space: O(n) for the new array. No memory yoga needed.
• If you square, then sort, you are back to O(n log n)—fastest way to fail a technical screen.

🧠 Interviewer Brain-Tattoo

“If squaring a sorted array makes you want to sort again, take the hint: two pointers beat brute force, every time.”