Sorted Squared Array

• Time : O(n)
• Space : O(1)

#include <vector>
using namespace std;

vector<int> sortedSquaredArray(vector<int> array) {
    auto mi = min_element(begin(array), end(array), [](int a, int b) {
        return abs(a) < abs(b);
    }) - begin(array);
    int l = mi, r = l + 1, n = array.size();
    vector<int> res;
    while(l >= 0 and r < n) {
        if(abs(array[l]) > abs(array[r])) {
            res.push_back(array[r] * array[r]); r++;
        } else {
            res.push_back(array[l] * array[l]); l--;
        }
    }
    while(l >= 0) {
        res.push_back(array[l] * array[l]); l--;
    }
    while(r < n) {
        res.push_back(array[r] * array[r]); r++;
    }
    return res;
}