Squares of Sorted Array [Easy] — Two Pointers Fill from End

Problem Statement

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

Input: [-4,-1,0,3,10] → Output: [0,1,9,16,100]

Intuition

Largest squares come from the most extreme ends. Use two pointers L, R; fill result array from the back, always taking the larger square.

Solutions

C

int* sortedSquares(int* nums, int n, int* returnSize) {
    *returnSize=n;
    int* res=malloc(n*sizeof(int));
    int l=0, r=n-1, i=n-1;
    while (l<=r) {
        int sl=nums[l]*nums[l], sr=nums[r]*nums[r];
        res[i--] = sl>sr ? (l++, sl) : (r--, sr);
    }
    return res;
}

C++

vector<int> sortedSquares(vector<int>& nums) {
    int n=nums.size(), l=0, r=n-1, i=n-1;
    vector<int> res(n);
    while (l<=r) {
        int sl=nums[l]*nums[l], sr=nums[r]*nums[r];
        if (sl>sr) { res[i--]=sl; l++; }
        else       { res[i--]=sr; r--; }
    }
    return res;
}

Java

public int[] sortedSquares(int[] nums) {
    int n=nums.length, l=0, r=n-1, i=n-1;
    int[] res=new int[n];
    while (l<=r) {
        int sl=nums[l]*nums[l], sr=nums[r]*nums[r];
        if (sl>sr) { res[i--]=sl; l++; }
        else       { res[i--]=sr; r--; }
    }
    return res;
}

JavaScript

var sortedSquares = function(nums) {
    const n=nums.length, res=new Array(n);
    let l=0, r=n-1, i=n-1;
    while (l<=r) {
        const sl=nums[l]**2, sr=nums[r]**2;
        if (sl>sr) { res[i--]=sl; l++; }
        else       { res[i--]=sr; r--; }
    }
    return res;
};

Python

def sortedSquares(nums: list[int]) -> list[int]:
    n = len(nums)
    res = [0] * n
    l, r, i = 0, n-1, n-1
    while l <= r:
        sl, sr = nums[l]**2, nums[r]**2
        if sl > sr:
            res[i] = sl; l += 1
        else:
            res[i] = sr; r -= 1
        i -= 1
    return res

Complexity

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