30 Days of Code [Day 25]

07 Sep 2021

QUESTION : 977. Squares of a Sorted Array

#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define pf push_front
#define mp make_pair
#define all(v) v.begin(), v.end()
#define fo(i,s,n) for(int i=s;i<n;++i)
#define of(i,s,n) for(int i=s-1;i>=n;--i)
#define fv(V) for( auto &it : V )
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        priority_queue<int, vi, greater<int>> pq;
        fv(nums){
            pq.push(it*it);
        }
        vi res;
        while(!pq.empty()){
            res.pb(pq.top());
            pq.pop();
        }
        return res;
    }
};

O(n)

#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define pf push_front
#define mp make_pair
#define all(v) v.begin(), v.end()
#define fo(i,s,n) for(int i=s;i<n;++i)
#define of(i,s,n) for(int i=s-1;i>=n;--i)
#define fv(V) for( auto &it : V )
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int index;
        fo(i,0,nums.size()){
            if(nums[i] >= 0){
                index = i;
                break;
            }
        }
        int f = index, b = index-1;
        vi res;
        while(b >= 0 || f < nums.size()){
            if(b >= 0 && f < nums.size()){
                if(nums[f] <= abs(nums[b])){
                    res.pb(nums[f]*nums[f]);
                    f++;
                }
                else{
                    res.pb(abs(nums[b])*abs(nums[b]));
                    b--;
                }
            }
            else if(f < nums.size()){
                res.pb(nums[f]*nums[f]);
                f++;
            }
            else{
                res.pb(abs(nums[b])*abs(nums[b]));
                b--;
            }
        }
        return res;
    }
};