977. Squares of a Sorted Array

The description of the 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.

example
Input: $nums=[-4,-1,0,3,10]$
Output: $[0,1,9,16,100]$
Explanation: After squaring, the array becomes $[16,1,0,9,100].$
After sorting, it becomoes $[0,1,9,16,100]$

The solutions

The solution1 the most intuitive one

1. get the squares of each element in $nums$
2. sort the results in increasing way
   codes

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> res;
        int n = nums.size();
        for (auto num : nums) {
            res.push_back(num * num);
        }
        sort(res.begin(), res.end());
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

The solution 2 using two pointers

1. make sure three ponter indexes
2. one points the left the $nums$, another pointing the right side
3. the last pointer points the return vector
   codes

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> res = nums;
        int k = nums.size() - 1; // the index in the return vector
        for (int i = 0, j = k; i <= j; ) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                res[k--] = nums[i] * nums[i];
                ++i;
            } else {
                res[k--] = nums[j] * nums[j];
                --j;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17