class Solution {
public:

    static bool comp(pair<int,int> a, pair<int,int> b)
    {
        return a.first < b.first;
    }

    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        // Naive method
        // for(int i = 0;i<n-1;++i)
        // {
        //     for(int j = i+1; j<n; ++j)
        //     {
        //         if(nums[i] + nums[j] == target)
        //             return vector<int>({i,j});
        //     }
        // }
        // return nums;

        // Optimised
        vector<pair<int,int>> demo;
        for(int i = 0;i<n;++i)
            demo.push_back({nums[i],i});
        
        sort(demo.begin(),demo.end(),comp);

        int i = 0, j = n-1;
        while(i<j)
        {
            int curr = demo[i].first + demo[j].first;
            if(curr == target)
                return {demo[i].second,demo[j].second};
            else if(curr < target)
                ++i;
            else
                --j;
        }
        return {};
    }
};