◻️977. Squares of a Sorted Array (easy)

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

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]

---

Solutions

Optimised (2 Pointer)

Runtime 21 ms Memory 28.59 MB

// From Neetcode

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        const int n = nums.size();
        if(n <= 1) return vector<int>{(nums[0]*nums[0])};
        vector<int> ans(n);
        int ptr1=0, ptr2=n-1;
        for(int i=n-1; i>=0; i--){
            if(abs(nums[ptr1]) > abs(nums[ptr2])){
                ans[i]=nums[ptr1]*nums[ptr1];
                ptr1++;
            }
            else{
                ans[i]=nums[ptr2]*nums[ptr2];
                ptr2--;
            }
        }
        return ans;        
    }
};

Optimised

• Time: O(n)

• Space: O(n)

Runtime 26 ms Memory 28.68 MB

// From https://walkccc.me/LeetCode/problems/977/

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        int r=n-1, i=n-1, l=0;
        for(l,r; l<=r;){
            if(abs(nums[l])>abs(nums[r])){
                ans[i--]=nums[l]*nums[l++];
            }
            else{
                ans[i--]=nums[r]*nums[r--];
            }
        }
        return ans;
    }
};