Squares of a Sorted Array

Problem

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

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

Constraints

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

Solution

The problem Squares of a Sorted Array can be solved using a divide and conquer algorithm. By separating the given array into negative and positive integers, the problem becomes equivalent to merging 2 sorted arrays.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    vector<int> sortedSquares(vector<int> &nums)
    {
        vector<int> ret(nums.size());

        int left = 0, right = nums.size() - 1;
        for (int i = nums.size(); i > 0; i--)
        {
            int square;
            if (abs(nums[left]) < abs(nums[right]))
                square = nums[right--];
            else
                square = nums[left++];

            ret[i - 1] = square * square;
        }

        return ret;
    }
};