package LeetCode;

public class LeetCode167 {

    //https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

    /**
     * 
     *
     * @param numbers
     * @param target
     * @return
     */
    // : O(n^2)
    // : O(1)
    public int[] twoSum(int[] numbers, int target) {

        if (numbers.length < 2 /*|| !isSorted(numbers)*/)
            throw new IllegalArgumentException("Illegal argument numbers");

        for (int i = 0; i < numbers.length; i++)
            for (int j = i + 1; j < numbers.length; j++)
                if (numbers[i] + numbers[j] == target) {
                    int[] res = {i + 1, j + 1};
                    return res;
                }

        throw new IllegalStateException("The input has no solution");
    }

    // 
    // : O(nlogn)
    // : O(1)
    public int[] twoSum2(int[] numbers, int target) {

        if (numbers.length < 2 /*|| !isSorted(numbers)*/)
            throw new IllegalArgumentException("Illegal argument numbers");
        for (int i = 0; i < numbers.length - 1; i++) {
            int j = binarySearch(numbers, i + 1, numbers.length - 1, target - numbers[i]);
            if (j != -1) {
                // 1+1
                int[] res = {i + 1, j + 1};
                return res;
            }
        }

        throw new IllegalStateException("The input has no solution");
    }

    private int binarySearch(int[] nums, int l, int r, int target) {

        if (l < 0 || l > nums.length)
            throw new IllegalArgumentException("l is out of bound");

        if (r < 0 || r > nums.length)
            throw new IllegalArgumentException("r is out of bound");

        while (l  nums[mid])
                l = mid + 1;
            else
                r = mid - 1;
        }

        return -1;
    }

    // 
    // : O(n)
    // : O(1)
    public int[] twoSum3(int[] numbers, int target) {

        if (numbers.length < 2 /*|| !isSorted(numbers)*/)
            throw new IllegalArgumentException("Illegal argument numbers");

        int l = 0, r = numbers.length - 1;
        while (l < r) {

            if (numbers[l] + numbers[r] == target) {
                int[] res = {l + 1, r + 1};
                return res;
            } else if (numbers[l] + numbers[r] < target)
                l++;
            else // numbers[l] + numbers[r] > target
                r--;
        }

        throw new IllegalStateException("The input has no solution");
    }

}