Squares of a Sorted Array

Squares of a Sorted Array

What is this problem about?

The Squares of a Sorted Array coding problem asks you to take an array of integers that is already sorted in non-decreasing order and return a new array containing the squares of each number, also sorted in non-decreasing order. The main challenge arises from the presence of negative numbers, whose squares become positive and can potentially be larger than the squares of positive numbers later in the array.

Why is this asked in interviews?

This "Easy" problem is a staple at companies like Apple, Uber, and Microsoft. It's designed to see if a candidate can optimize beyond a simple $O(N \log N)$ sorting approach. While you could just square everything and sort it, interviewers are looking for a linear $O(N)$ solution that takes advantage of the fact that the original array is already sorted. It tests your ability to use the Two Pointers interview pattern effectively.

Algorithmic pattern used

The optimal Algorithmic pattern used here is Two Pointers. Since the largest squares must come from either the very beginning (large negative numbers) or the very end (large positive numbers) of the sorted array, you place one pointer at the start and one at the end. You compare the absolute values (or the squares) of the elements at these pointers, place the larger one at the end of your result array, and move the corresponding pointer inward.

Example explanation (use your own example)

Suppose you have the array [-4, -1, 0, 3, 10].

1. Left pointer at -4, Right pointer at 10. Squares: 16 and 100.
2. 100 is larger. Result: [?, ?, ?, ?, 100]. Move right pointer to 3.
3. Left pointer at -4, Right pointer at 3. Squares: 16 and 9.
4. 16 is larger. Result: [?, ?, ?, 16, 100]. Move left pointer to -1.
5. Left pointer at -1, Right pointer at 3. Squares: 1 and 9.
6. 9 is larger. Result: [?, ?, 9, 16, 100]. Move right pointer to 0.
7. Continuing this, you get [0, 1, 9, 16, 100].

Common mistakes candidates make

• Inefficient Sorting: Squaring every element and then calling a standard sort function, which is $O(N \log N)$ instead of $O(N)$.
• Pointer logic errors: Moving the wrong pointer or failing to handle the case where the pointers meet.
• Extra Space: Not realizing that a new result array is necessary (unless you can somehow square in place, which is difficult for this specific problem due to the sorting requirement).
• Ignoring Negatives: Forgetting that -5 squared is larger than 2 squared.

Interview preparation tip

Whenever you have a sorted array and are asked to produce another sorted array based on some transformation of the values, always consider the Two Pointers interview pattern. It's the most common way to achieve linear time complexity in such scenarios.