Mayank Arora

Posted on

# 977. Squares of a Sorted Array [Leetcode][C++]

All suggestions are welcome. Please upvote if you like it. Thank you.

Leetcode Problem Link: 977. Squares of a Sorted Array

Brute Force Solution:

``````class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
// Brute Force Solution Time O(NlogN) & Auxiliary Space O(1)
int len=nums.size();
for(int i=0;i<len;i++)
nums[i]=nums[i]*nums[i];
sort(nums.begin(),nums.end());
return nums;
}
};
``````

Efficient Solution:

``````class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
// Efficient Solution Time O(N) & Auxiliary Space O(1)
// Two Pointer Method
int len=nums.size(), lt=0, rt=len;
vector<int> res;
// Find index of first positive vector element & position right pointer
for(int i=0;i<len;i++){
if(nums[i]>=0){
rt=i;
break;
}
}
// Position left pointer at smallest negative vector element
lt=rt-1;
while(lt>=0 && rt<=len-1){
// Compare elements at left & right index and push the square of
// the smaller element in the resultant vector in ascending order
// and reposition the left(decrement) & right(increment) pointers
if(abs(nums[lt])<nums[rt]){
res.push_back(nums[lt]*nums[lt]);
lt--;
}
else if(abs(nums[lt])>nums[rt]){
res.push_back(nums[rt]*nums[rt]);
rt++;
}
else{
res.push_back(nums[lt]*nums[lt]);
lt--;
res.push_back(nums[rt]*nums[rt]);
rt++;
}
}
// Push the square of the element in the resultant vector for the
// case of unvisited elements
while(lt>-1){
res.push_back(nums[lt]*nums[lt]);
lt--;
}
while(rt<len){
res.push_back(nums[rt]*nums[rt]);
rt++;
}
return res;
}
};

``````

All suggestions are welcome. Please upvote if you like it. Thank you.

DEV Community

Timeless DEV post...

## Git Concepts I Wish I Knew Years Ago

The most used technology by developers is not Javascript.

It's not Python or HTML.

It hardly even gets mentioned in interviews or listed as a pre-requisite for jobs.

I'm talking about Git and version control of course.