How to Solve Squares of a Sorted Array

This problem can be solved efficiently by leveraging the two-pointer technique to square each element in a sorted array and then merge them in non-decreasing order. This approach avoids the need for sorting after squaring, ensuring optimal performance for large inputs. The core idea is to track the largest elements from both ends of the array using two pointers and handle the merging step appropriately.

Problem Statement

Given a sorted integer array, nums, return an array of the squares of each number in non-decreasing order. The solution should minimize extra space usage and avoid unnecessary sorting.

The key challenge is optimizing the process of squaring and sorting the elements without directly sorting the array after squaring, as the input array is already sorted.

Examples

Example 1

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

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

After squaring, the array becomes [16,1,0,9,100]. After sorting, it becomes [0,1,9,16,100].

Example 2

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

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

Example details omitted.

Constraints

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums is sorted in non-decreasing order.

Solution Approach

Two-Pointer Approach

Start by initializing two pointers, one at the beginning and one at the end of the array. Compare the absolute values of the numbers at both ends, square the larger number, and place the square in the result array. Move the pointers inward, repeating the process until all elements are processed.

Merging the Results

As you square the elements from both ends of the array, fill the result array from the back (largest index), ensuring that the resulting array is filled in non-decreasing order without the need for a separate sorting step.

Time and Space Complexity Considerations

This approach ensures a time complexity of O(n) where n is the length of the array. Space complexity can be O(n) if an additional result array is used, or O(1) if the input array is modified in place.

Complexity Analysis

The two-pointer approach works in linear time, O(n), because each element is processed exactly once. Space complexity is O(n) for the result array, but can be optimized to O(1) if we modify the input array in place.

What Interviewers Usually Probe

• Look for clarity in how the candidate explains the two-pointer method and its impact on the algorithm's time complexity.
• The ability to optimize space usage while maintaining linear time is crucial.
• Pay attention to how well the candidate understands the failure mode of directly sorting the squared elements.

Common Pitfalls or Variants

Common pitfalls

• Failing to maintain the two-pointer invariant, which may lead to incorrect results or inefficient solutions.
• Incorrectly using extra space for sorting the squared numbers, which can lead to an O(n log n) time complexity.
• Not handling edge cases, such as arrays with a single element or all non-negative numbers.

Follow-up variants

• Modify the approach to work in-place without using extra space for a result array.
• Handle arrays with both positive and negative numbers, ensuring that the squares are correctly placed in non-decreasing order.
• Adapt the solution to work with larger inputs by considering more efficient memory management.

How GhostInterview Helps

• GhostInterview provides clear guidance on implementing the two-pointer technique, optimizing the approach for time and space complexity.
• Through the solution steps, GhostInterview ensures you avoid common pitfalls like unnecessary sorting or incorrect pointer movement.
• With real-time hints and corrections, GhostInterview helps refine your understanding of how to track and merge squared values in an optimal manner.

Topic Pages

• Array
• Two Pointers
• Sorting

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the two-pointer approach in the Squares of a Sorted Array problem?

The two-pointer approach involves using two pointers, one at the start and one at the end of the sorted array. You square the larger number at both ends and place the square at the correct position in the result array.

Why is the time complexity O(n) for the two-pointer solution?

Each element of the array is processed once, either by moving the left or right pointer, ensuring a linear time complexity of O(n).

Can we solve the Squares of a Sorted Array problem without extra space?

Yes, it is possible to solve the problem in-place by modifying the input array to hold the squared elements in non-decreasing order.

How does the solution handle arrays with negative numbers?

The two-pointer technique works by comparing the absolute values of the numbers, so it efficiently handles arrays with both negative and positive numbers.

What are common mistakes when solving this problem?

Common mistakes include failing to use the two-pointer technique correctly, sorting the array after squaring, and not handling edge cases like arrays with one element.