class Solution {
    /** Bruite force, O(N) O(N) */
    public int[] twoSum(int[] nums, int target) {
        int[] arr = new int[]{-1,-1};

        Map<Integer, Integer> map = new HashMap<>();

        for(int i=0; i <nums.length; i++)
        {
            int diff = target - nums[i];

            if(map.containsKey(diff))
            {
                arr[0] = map.get(diff);
                arr[1] = i;
                break;
            }
            else
                map.put(nums[i], i);
        }
        return arr;
    }

	/** Two pointer approach, O(N) O(1) */
    // works only if array has positive elements
    public int[] twoSum(int[] nums, int target) {
        int i=0;
        int j=nums.length-1;
        int[] arr = new int[]{-1,-1};

        while(i < j)
        {
            if(nums[i] + nums[j] == target)
            {
                arr[0] = i;
                arr[1] = j;
                break;
            }
            else if(nums[i] + nums[j] < target)
                i++;
            else if(nums[i] + nums[j] > target)
                j--;
        }
        return arr;
    }
}