26. Leetcode 977. Squares of a Sorted Array.md

977. Squares of a Sorted Array

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 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.

---

Solutions

Method1: Merging

/*
Method1: Merge
the idea is to use the merge part from the merge sort

For example, with [-3, -2, -1, 4, 5, 6], we have the negative part [-3, -2, -1] with squares [9, 4, 1], 
and the positive part [4, 5, 6] with squares [16, 25, 36]. 
Our strategy is to iterate over the negative part in reverse, and the positive part in the forward direction.

//T(n) = O(n)
//S(n) = O(1)
*/

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        vector<int> res;
        int len = A.size();
        int postive = 0;
        int nagtive = len - 1;
        
        /*
        note: the following statements will not work 
        while (postive < len && A[postive++] < 0);
        while (nagtive >= 0 && A[nagtive--] >= 0);
        
        they will not work because postive and nagtive will increase or decrease regardless
        the condition was evaluated to true or false
        */
        
        while (postive < len && A[postive] < 0) { postive++; };
        while (nagtive >= 0 && A[nagtive] >= 0) { nagtive--; };

        while (postive < len || nagtive >= 0) {
            int pos = INT_MAX;
            int nag = INT_MAX;
            if (postive < len) {
                pos = A[postive];
            }
            if (nagtive >= 0) {
                nag = A[nagtive];
            }

            if (pow(pos, 2) < pow(nag, 2)) {
                res.push_back(pow(pos, 2));
                postive++;
            }
            else {
                res.push_back(pow(nag, 2));
                nagtive--;
            }
            while (postive < len && A[postive] < 0) { postive++; };
            while (nagtive >= 0 && A[nagtive] > 0) { nagtive--; };
        }
        return res;
    }
};