Two Pointer SquareArray Problem

#include <bits/stdc++.h>
using namespace std;
vector<intsortedSquares(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;
}

Comments

  1. https://leetcode.com/problems/squares-of-a-sorted-array/submissions/

    ReplyDelete

Post a Comment

Popular Posts