1019. Squares of a Sorted Array

• Difficulty: Easy

• Topics: Array, Two Pointers

• Similar Questions:

  • Merge Sorted Array

  • Sort Transformed Array

Problem:

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

Example 1:

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

Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

1. 1 <= A.length <= 10000
2. -10000 <= A[i] <= 10000
3. A is sorted in non-decreasing order.

Solutions:

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int right = distance(A.begin(), lower_bound(A.begin(), A.end(), 0));
        int left = right - 1;

        vector<int> ret;
        while (left >= 0 && right < A.size()) {
            if (abs(A[left]) <= abs(A[right])) {
                ret.push_back(A[left] * A[left]);
                --left;
            } else {
                ret.push_back(A[right] * A[right]);
                ++right;
            }
        }

        if (left < 0) {
            while (right < A.size()) {
                ret.push_back(A[right] * A[right]);
                ++right;
            }
        } else {
            while (left >= 0) {
                ret.push_back(A[left] * A[left]);
                --left;
            }
        }

        return ret;

    }
};