What is the time complexity of Brute Force with Sorting approach?

The time complexity is O(n log n) due to the sorting step after squaring all elements.

What is the time complexity of Two Pointers approach?

The time complexity is O(n) as we only traverse the array once with two pointers.

Why does the Two Pointers approach work?

Since the array is sorted, the largest squares will be at the ends (most negative or most positive values). By comparing from both ends, we can build the sorted result from largest to smallest.

What is the space complexity of both approaches?

Both approaches use O(n) space for the result array. The Two Pointers approach is optimal in time complexity.

Squares of a Sorted Array

Difficulty: Easy | Acceptance: 73.70% | Paid: No Topics: Array, Two Pointers, Sorting

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

Examples
Constraints
Brute Force with Sorting
Two Pointers

Examples

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: 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]

Constraints

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

Brute Force with Sorting

Intuition Square each element individually, then sort the resulting array to get the final sorted order.

Steps

Iterate through the array and square each element
Sort the squared array in non-decreasing order
Return the sorted array

python

class Solution:
    def sortedSquares(self, nums: List[int]) -&gt; List[int]:
        return sorted(x * x for x in nums)

Complexity

Time: O(n log n)
Space: O(n) or O(1) depending on language implementation
Notes: Simple but not optimal due to sorting overhead

Two Pointers

Intuition Since the array is sorted, the largest squares will be at the ends (most negative or most positive values). Use two pointers from both ends and fill the result array from the back.

Steps

Initialize two pointers at the start and end of the array
Compare squares of elements at both pointers
Place the larger square at the current end position of result array
Move the pointer inward and repeat until all elements are processed

python

class Solution:
    def sortedSquares(self, nums: List[int]) -&gt; List[int]:
        n = len(nums)
        result = [0] * n
        left, right = 0, n - 1
        pos = n - 1
        
        while left &lt;= right:
            left_sq = nums[left] * nums[left]
            right_sq = nums[right] * nums[right]
            
            if left_sq &gt; right_sq:
                result[pos] = left_sq
                left += 1
            else:
                result[pos] = right_sq
                right -= 1
            pos -= 1
        
        return result

Complexity

Time: O(n)
Space: O(n) for the result array
Notes: Optimal solution that leverages the sorted input property