Two Pointer SquareArray Problem
#include <bits/stdc++.h>
using namespace std;
vector<int> sortedSquares(vector<int>& nums) {
// if no negative : return as it is.
// if no posiitve : return reverse.
// else follow two pointer.
vector<int> ans;
int l;
int r=nums.size();
for(int i=0;i<nums.size();i++){
if(nums[i] >= 0){
r = i;
break;
}
}
l = r-1;
while(l != -1 && r != nums.size()){
if(abs(nums[l]) < nums[r]){
ans.push_back(nums[l]*nums[l]);
l--;
}
else{
ans.push_back(nums[r]*nums[r]);
r++;
}
}
if(l == -1){
while(r!=nums.size()){
ans.push_back(nums[r]*nums[r]);
r++;
}
}
else if(r == nums.size()){
while(l != -1){
ans.push_back(nums[l]*nums[l]);
l--;
}
}
return ans;
}
int main(){
// algo:
// 1. left pointer at last negative and start moving in left.
// 2. right pointer at first positive(=0) and start
// moving in right.
// 3. since the array is sorted, we will be comapring
// a[l] & a[r] at each turn and push the smaller one.
// if any pointer gets exhausted, we will follow
// same procedure for single pointer without comparing.
int n;
cin >> n;
vector<int> a;
for(int i=0;i<n;i++){
int x;
cin >> x;
a.push_back(x);
}
vector<int> ans;
ans = sortedSquares(a);
for(int i=0;i<n;i++){
cout << ans[i] << " ";
}
return 0;
}
https://leetcode.com/problems/squares-of-a-sorted-array/submissions/
ReplyDelete