Squares of a Sorted Array

Problem Statement

Given an integer array nums sorted in non-decreasing order (it may contain negatives), return an array of 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]

Two Pointer Approach

The largest square is always at one of the two ends (because negatives can have large magnitude). Use two pointers at both ends, compare absolute values, and write the bigger square into the result from the back.

Complexity

• Time: O(n)
• Space: O(n) for the output

Solution Code

Python

def sortedSquares(nums):
    n = len(nums)
    res = [0] * n
    left, right = 0, n - 1
    for pos in range(n - 1, -1, -1):
        if abs(nums[left]) > abs(nums[right]):
            res[pos] = nums[left] ** 2
            left += 1
        else:
            res[pos] = nums[right] ** 2
            right -= 1
    return res

Java

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

C++

vector<int> sortedSquares(vector<int>& nums) {
    int n = nums.size(), left = 0, right = n - 1;
    vector<int> res(n);
    for (int pos = n - 1; pos >= 0; pos--) {
        int lv = nums[left], rv = nums[right];
        if (abs(lv) > abs(rv)) { res[pos] = lv * lv; left++; }
        else { res[pos] = rv * rv; right--; }
    }
    return res;
}

Key Takeaways

• Filling the result from the back avoids a final sort.
• Compare magnitudes with abs(), not raw values.
• Beats the naive square-then-sort O(n log n) approach.