#include <bits/stdc++.h>

using namespace std;

// Problem 1. Two Sum

// Given an array of integers nums and an integer target, return
// indices of the two numbers such that they add up to target.

// You may assume that each input would have exactly one solution, and
// you may not use the same element twice.

// You can return the answer in any order.

class Solution {
public:
    // This solution doesn't work properly
    vector<int> twoSum(vector<int>& nums, int target)
    {
        // maintain indicies of original vector
        multimap<int,int> indexMap;
        for (int i = 0; i < (int)nums.size(); i++)
            indexMap.insert(pair<int,int>{nums[i],i});

        cout << "indexMap: ";
        for (auto& i: indexMap)
            cout << i.first << " -> " << i.second << ", ";
        cout << endl;
        
        sort(nums.begin(), nums.end()); // O(N·log(N))
        cout << "sorted: ";
        for (auto& i: nums)
            cout << i << " ";
        cout << endl;

        int beginIndex = 0, endIndex = nums.size() - 1;
        int sum = nums[beginIndex] + nums[endIndex];
        cout << " init [" << beginIndex << "," << endIndex << "] [" << nums[beginIndex] << "," << nums[endIndex] << "] sum: " << sum << " target: " << target << endl;

        if (sum == target)
            goto DONE;        

        while (nums[beginIndex] > 0 && nums[endIndex] >= target)
            endIndex--;

        // while (nums[beginIndex] < 0 && nums[endIndex] < target)
        //     beginIndex++;
        
        sum = nums[beginIndex] + nums[endIndex];
        cout << "start [" << beginIndex << "," << endIndex << "] [" << nums[beginIndex] << "," << nums[endIndex] << "] sum: " << sum << " target: " << target << endl;

        while ( sum != target && beginIndex < endIndex)
        {
            if (sum < target && target > 0)
                beginIndex++;            
            else
                endIndex--;
            
            sum = nums[beginIndex] + nums[endIndex];
            cout << "      [" << beginIndex << "," << endIndex << "] [" << nums[beginIndex] << "," << nums[endIndex] << "] sum: " << sum << " target: " << target << endl;
        }

    DONE:

        int begin, end;
        if (nums[beginIndex] == nums[endIndex]) // sum is of two equal numbers
        {
            auto range = indexMap.lower_bound(nums[beginIndex]);
            begin = range->second;
            range++;
            end = range->second;
        }
        else
        {            
            auto iter = indexMap.find(nums[beginIndex]);
            begin = iter->second;
            iter = indexMap.find(nums[endIndex]);
            end = iter->second;
        }

        vector<int> result{begin,end};
        return result;
    }
};


int main()
{
    Solution s;
    vector<tuple<int, vector<int>, pair<int,int>>> testCases = {
    // target nums              expected
    // ------ -----------       ------
        {9,   {2,7,11,15},      {0,1}},
        {6,   {3,2,4},          {1,2}},
        {6,   {3,3},            {0,1}},
        {0,   {0,4,3,0},        {0,3}},
        {-8,  {-1,-2,-3,-4,-5}, {2,4}},
        {0,   {-3,4,3,90},      {0,2}},
        {9,   {-10,7,19,15},    {0,2}},
        {0,   {0,3,-3,4,-1},    {1,2}},
        {-19, {-10,-1,-18,-19}, {1,2}},
        {-1,  {0,3,-3,4,-1},    {0,4}},
    };

    for (auto& tc: testCases)
    {
        cout << "target: " << get<0>(tc) << " nums: ";
        for (auto& num: get<1>(tc))
            cout << num << " ";
        cout << endl;
        
        vector<int> indices = s.twoSum(get<1>(tc), get<0>(tc));
        sort(indices.begin(), indices.end());        

        cout << "result: ";
        for (auto& i: indices)
            cout << i << " ";
        cout << " expected: " << get<2>(tc).first << " " << get<2>(tc).second;
        if (indices.at(0) != get<2>(tc).first || indices.at(1) != get<2>(tc).second)
            cout << "\nFailed";
        cout << "\n-------------" << endl;
    }
}